Comment construire un index inversé simple?

Je veux construire une simple fonction d'indexation du moteur de recherche, sans API, comme Lucene. Dans l'index inversé, j'ai juste besoin d'enregistrer des informations de base de chaque mot, par exemple docID, la position et la freqence.

Maintenant, j'ai plusieurs questions:

  1. Quel type de structure de données est souvent utilisé pour la construction d'index inversé? Multidimensionnelle liste?
  2. Après la construction de l'index, la façon de l'écrire dans les fichiers? Quel type de format dans le fichier? Comme un tableau? Comme le dessin d'une table d'index sur le papier?

source d'informationauteur Munichong

  1. 29

    Vous pouvez voir un très simple de mise en œuvre de l'index inversé et de recherche en TinySearchEngine.

    Pour votre première question, si vous voulez construire un simple (en mémoire) index inversé à la simplicité de la structure de données est une table de Hachage de la carte comme ceci:

    val invertedIndex = new collection.mutable.HashMap[String, List[Posting]]

    ou Java-esque:

    HashMap<String, List<Posting>> invertedIndex = new HashMap<String, List<Postring>>();

    Le hachage des cartes à chaque terme/mot/jeton à une liste de Messages. Un Posting est juste un objet qui représente une occurrence d'un mot à l'intérieur d'un document:

    case class Posting(docId:Int, var termFrequency:Int)

    De l'indexation d'un nouveau document est juste une question de la segmentation (séparer les jetons/mots) et pour chaque jeton d'insérer un nouvel Affichage dans la Liste correcte de la valeur de hachage de la carte. Bien sûr, si une écriture existe déjà pour ce terme dans l'docId, vous augmentez la termFrequency. Il y a d'autres façons de le faire. Dans la mémoire de l'index inversés c'est OK, mais pour l'index sur disque que vous auriez probablement souhaitez insérer Postings la termFrequency au lieu de le mettre à jour à chaque fois.

    Concernant votre deuxième question, il y a normalement deux cas:

    (1) vous avez (presque) immuable de l'index. Vous indexer toutes vos données une fois et si vous avez de nouvelles données, vous pouvez simplement réindexer. Il n'est pas nécessaire en temps réel ou l'indexation de nombreuses fois en une heure, par exemple.

    (2) de nouveaux documents arrivent tout le temps, et vous avez besoin de rechercher les nouveaux arrivés, les documents dès que possible.

    Pour le cas (1), vous pouvez disposer d'au moins 2 fichiers:

    1 - L'Index Inversé fichier. Il énumère, pour chaque terme, toutes les Postings (docId/termFrequency paires). Ici représenté en texte brut, mais normalement stockées en tant que données binaires.

     Term1<docId1,termFreq><docId2,termFreq><docId3,termFreq><docId4,termFreq><docId5,termFreq><docId6,termFreq><docId7,termFreq>
 Term2<docId3,termFreq><docId5,termFreq><docId9,termFreq><docId10,termFreq><docId11,termFreq>
 Term3<docId1,termFreq><docId3,termFreq><docId10,termFreq>
 Term4<docId5,termFreq><docId7,termFreq><docId10,termFreq><docId12,termFreq>
 ...
 TermN<docId5,termFreq><docId7,termFreq>

    2 - Le décalage de fichier. Stocke pour chaque terme le décalage de trouver inversé liste dans l'index inversé fichier. Ici, je suis représentant le décalage dans les personnages, mais vous aurez normalement stocker des données binaires, de sorte que le décalage est en octets. Ce fichier peut être chargé en mémoire au démarrage. Lorsque vous avez besoin de chercher un terme inversé liste, vous recherche de son décalage et de lire l'inverse de la liste dans le fichier.

    Term1 -> 0
Term2 -> 126
Term3 -> 222
....

    Avec ces 2 fichiers, vous pouvez (et en général) de fichier(s) pour stocker chaque terme de la TSAHAL et chaque document de la norme.

    Pour le cas (2), je vais essayer d'expliquer brièvement comment Lucene (et, par conséquent, Solr et ElasticSearch) le faire.

    Le format de fichier peut être la même, comme expliqué ci-dessus. La principale différence est que lorsque vous l'indice de nouveaux documents dans des systèmes comme Lucene au lieu de la reconstruction de l'index à partir de zéro, ils suffit de créer un nouveau compte avec seulement les nouveaux documents. Donc, chaque fois que vous avez de l'indice de quelque chose, vous le faites dans une nouvelle séparés index.

    Pour effectuer une requête dans ce "coupée en deux" de l'index, vous pouvez exécuter la requête à l'encontre de chacun des différents index (en parallèle) et de fusionner les résultats de l'ensemble avant de retourner à l'utilisateur.

    Lucene appelle cela un "peu" indices segments.

    L'évidente préoccupation ici est que vous aurez beaucoup de petits segments très rapide. Pour éviter cela, vous aurez besoin d'une politique pour la fusion des segments et de créer des segments plus larges. Par exemple, si vous avez plus de N segments vous pouvez choisir de fusionner tous les segments plus petits que 10 KBs ensemble.