ngramindexering

N-gramindexering är en teknik inom textsökning som används för att stödja snabb substringsökning i stora textkorpus genom att indexera alla n-gram, det vill säga substrings av längd n, som förekommer i dokumenten. Denna metod gör det möjligt att hitta dokument som innehåller en given sekvens av tecken även om exakta ord skiljer sig något eller ordningen varierar.

Hur det fungerar: man väljer ett värde på n och extraherar för varje dokument alla n-gram med ett löpande fönster över texten. Dessa n-gram lagras i en inverted index som mappar varje n-gram till en lista över dokument (och ofta positionsinformation eller frekvenser) där det förekommer. För bättre prestanda används ofta normalisering som liknar fallignering, borttagning av icke-texttecken eller Unicode-normalisering. Olika varianter inkluderar logik för flera n-värden, kompaktering av posten och hantering av längre fraser.

Frågebehandling och urval: när en användare lämnar en fråga genereras n-gram av frågan och relevanta dokument hämtas genom att kombinera postingslistorna för dessa n-gram. Resultatet rankas vanligtvis efter antal överensstämmande n-gram, kompletterat med viktning som tf-idf, BM25 eller liknande. N-gramindexering kan stödja exakt fras-sökning genom n-gram som sammanfaller med frasen i fråga, samt delvis matchning vid små avvikelser.

Fördelar och begränsningar: fördelen är snabb substringsökning och stöd för viss felmarginal i söktermer. begränsningar inkluderar stor minnes- och lagringskostnad samt att valet av n påverkar precision och recall; små n ger bredare täckning men fler falska träffar, stora n ökar kostnaden och kan missa mindre avvikelser. Vanliga användningsområden är sökmotorer, stavnings- och fuzzy-sökning, samt likhetssökningar och vissa biomedicinska tillämpningar.