Cum să căutați rapid o colecție de chei/valoare pe bază de șir

Bună ziua!

Am o listă de cuvinte de 200.000 intrări de șir, lungimea medie a șirului este de aproximativ 30 de caractere. Această listă de cuvinte este cheia și pentru fiecare cheie am un obiect de domeniu. Aș dori să găsesc obiectele de domeniu din această colecție, cunoscând doar o parte a cheii. I.E. șirul de căutare "kov" se potrivește, de exemplu, cu "stackoverflow".

În prezent, folosesc un arbore de căutare ternar (TST), care de obicei va găsi elementele în decurs de 100 de milisecunde. Acest lucru este totuși prea lent pentru cerințele mele. Implementarea TST ar putea fi îmbunătățită cu unele optimizări minore și aș putea încerca să echilibrez arborele. Dar m-am gândit că aceste lucruri nu mi-ar da 5x - 10x îmbunătățirea vitezei pe care mă îndrept. Presupun că motivul pentru a fi atât de lent este că practic trebuie să vizitez majoritatea nodurilor din copac.

Orice idei despre îmbunătățirea vitezei algoritmului? Există alți algoritmi la care ar trebui să mă uit?

Mulțumesc anticipat, Oskar

13
Învățat un lucru nou astăzi: Trie.
adăugat autor Will, sursa
În ce limbă lucrați? Aceste informații sunt necesare deoarece toate limbile nu gestionează căutările și colecțiile la fel
adăugat autor WolfmanDragon, sursa
Cred că ar trebui să fie "Trie" sau "Ternary Search Tree".
adăugat autor Tomalak, sursa
Asta e genul de intrebari pe care le iubesc: nimic nu incearca acum o provocare ... :-)
adăugat autor Konrad Rudolph, sursa
A. Ați putea explica modul în care ați reușit să utilizați TST pentru ceea ce pare a fi o căutare pentru ceva care nu este nici prefix, nici sufix? (În exemplul dvs., "kov" nu este nici prefix, nici sufix pentru "stackoverflow"), adică puteți să descrieți modul în care inserați elementele în TST? B. Puteți să vă spun - din nou, pentru exemplul dvs. specific de "kov" - să descrie modul în care implementarea funcției TST căutați știe cum/când să excludă anumite noduri de la inspecție (din nou, căutați un termen, nici prefix, nici sufix)?
adăugat autor MrCC, sursa

7 răspunsuri

Suffix Array și indexul q -gram

Dacă șirurile dvs. de caractere au o limită superioară a dimensiunii, vă recomandăm să utilizați un șir de sufixe : introduceți pur și simplu toate șirurile la aceeași lungime maximă folosind un caracter special (de ex. caracterul nul). Apoi concatenați toate șirurile și construiți un indice matrice de sufixe peste ele.

This gives you a lookup runtime of m * log n where m is the length of your query string and n is the overall length of your combined strings. If this still isn't good enough and your m has a fixed, small length, and your alphabet Σ is restricted in size (say, Σ < 128 different characters) you can additionally build a q-gram index. This will allow retrieval in constant time. However, the q-gram table requires Σm entries (= 8 MiB in the case of just 3 characters, and 1 GiB for 4 characters!).

Efectuarea indexului mai mic

S-ar putea să reduceți dimensiunea tabelului q (exponențial, în cel mai bun caz) prin ajustarea funcției hash. În loc să atribuiți un număr unic fiecărei q program posibile, este posibil să folosiți o funcție hash lossy. În acest caz, tabela ar trebui să stocheze liste de indicatori posibili de sufixi, în loc de o singură intrare de sufix, care corespunde unei potriviri exacte. Aceasta ar însemna că căutarea nu mai este constantă, totuși, deoarece toate intrările din listă ar trebui luate în considerare.

Apropo, nu sunt sigur dacă sunteți familiarizat cu modul în care funcționează un indice q , deoarece Internetul nu este util pentru acest subiect. Am menționat acest lucru înainte într-un alt subiect. Prin urmare, am inclus o descriere și un algoritm pentru construcție în teza mea de licență .

Dovada de concept

I've written a very small C# Dovada de concept (since you stated otherwise that you worked with C#). It works, however it is very slow for two reasons. First, the suffix array creation simply sorts the suffixes. This alone has runtime n2 log n. There are far superior methods. Worse, however, is the fact that I use SubString to obtain the suffixes. Unfortunately, .NET creates copies of the whole suffix for this. To use this code in practice, make sure that you use in-place methods which do not copy any data around unnecessarily. The same is true for retrieving the q-grams from the string.

Ar fi chiar mai bine să nu construim șirul m_Data folosit în exemplul meu. În schimb, puteți salva o referință la matricea originală și puteți simula toate accesările mele SubString lucrand pe acest matrice.

Totuși, este ușor de văzut că această implementare a așteptat în mod esențial regăsirea constantă a timpului (dacă dicționarul este bine comportat)! Aceasta este o realizare destul de mare, care nu poate fi bătută de un arbore de căutare!

class QGramIndex {
    private readonly int m_Maxlen;
    private readonly string m_Data;
    private readonly int m_Q;
    private int[] m_SA;
    private Dictionary m_Dir = new Dictionary();

    private struct StrCmp : IComparer {
        public readonly String Data;
        public StrCmp(string data) { Data = data; }
        public int Compare(int x, int y) {
            return string.CompareOrdinal(Data.Substring(x), Data.Substring(y));
        }
    }

    private readonly StrCmp cmp;

    public QGramIndex(IList strings, int maxlen, int q) {
        m_Maxlen = maxlen;
        m_Q = q;

        var sb = new StringBuilder(strings.Count * maxlen);
        foreach (string str in strings)
            sb.AppendFormat(str.PadRight(maxlen, '\u0000'));
        m_Data = sb.ToString();
        cmp = new StrCmp(m_Data);
        MakeSuffixArray();
        MakeIndex();
    }

    public int this[string s] { get { return FindInIndex(s); } }

    private void MakeSuffixArray() {
       //Approx. runtime: n^3 * log n!!!
       //But I claim the shortest ever implementation of a suffix array!
        m_SA = Enumerable.Range(0, m_Data.Length).ToArray();
        Array.Sort(m_SA, cmp);
    }

    private int FindInArray(int ith) {
        return Array.BinarySearch(m_SA, ith, cmp);
    }

    private int FindInIndex(string s) {
        int idx;
        if (!m_Dir.TryGetValue(s, out idx))
            return -1;
        return m_SA[idx]/m_Maxlen;
    }

    private string QGram(int i) {
        return i > m_Data.Length - m_Q ?
            m_Data.Substring(i) :
            m_Data.Substring(i, m_Q);
    }

    private void MakeIndex() {
        for (int i = 0; i < m_Data.Length; ++i) {
            int pos = FindInArray(i);
            if (pos < 0) continue;
            m_Dir[QGram(i)] = pos;
        }
    }
}

Exemplu de utilizare:

static void Main(string[] args) {
    var strings = new [] { "hello", "world", "this", "is", "a",
                           "funny", "test", "which", "i", "have",
                           "taken", "much", "too", "far", "already" };

    var index = new QGramIndex(strings, 10, 3);

    var tests = new [] { "xyz", "aki", "ake", "muc", "uch", "too", "fun", "est",
                         "hic", "ell", "llo", "his" };

    foreach (var str in tests) {
        int pos = index[str];
        if (pos > -1)
            Console.WriteLine("\"{0}\" found in \"{1}\".", str, strings[pos]);
        else
            Console.WriteLine("\"{0}\" not found.", str);
    }
}
13
adăugat
Există o modalitate de a împărți o masă q-gram, astfel încât să nu deranjeze discul folosind?
adăugat autor Will, sursa
Nu știu deloc. Cel mai bun pariu ar putea fi reducerea alfabetului prin împrăștierea mai multor caractere la aceeași cheie, reducând astfel dimensiunea tabelului exponențial. Totuși, trebuie să aveți grijă de coliziuni.
adăugat autor Konrad Rudolph, sursa
@ Rafał: Eu împletesc șiruri de caractere, așa că pot calcula indicele de a forma cu ușurință poziția în matricea sufixelor. Există și alte soluții, dar acestea necesită modificarea matricei sufixelor, ceea ce face ca construcția să fie mai dificilă.
adăugat autor Konrad Rudolph, sursa
O matrice de sufixe este mai bună decât un sufix, deoarece poate fi stocată mult mai eficient în spațiu. Mai important, aveți nevoie de un sufix array pentru a crea eficient indexul q-gram (cel puțin nu știu niciun algoritm pentru crearea unui indice q-gram pentru un arbore sufix).
adăugat autor Konrad Rudolph, sursa
@ Rafał: "Găsirea șirului original prin sufix ar trebui să fie rapid" - cum? Cu toate acestea, recunosc că umplerea șnurului nu este, în general, o modalitate bună. Ar fi mai bine să construim matricea sufixelor pe o serie de șiruri de caractere. Acest lucru este posibil, deși ușor mai greu. Voi actualiza textul în consecință.
adăugat autor Konrad Rudolph, sursa
@ Rafał: Aruncați o privire la postul meu de urmărire. Cu toate acestea, ca răspuns la propoziția log (N): rețineți că N-ul dvs. nu este doar 200.000, ci numărul sufixelor, care este mult mai mare.
adăugat autor Konrad Rudolph, sursa
De ce este necesară umplerea corzilor? Este sufixul mai bun decât arborele sufixului?
adăugat autor Rafał Dowgird, sursa
Puncte bune despre copac. Înapoi la padding - după cum înțeleg, puteți obține întregul sufix din tabel ("kov" -> "koverflow"). Găsirea șirului original prin sufix ar trebui să fie rapidă (sau chiar prin prefix, dacă construiți tabelul din șiruri inversate). Corect?
adăugat autor Rafał Dowgird, sursa
Puteți găsi șirul după sufix în O (log (N)) timp dacă păstrați o masă suplimentară a șirurilor sortate în ordinea inversă. Sau păstrați șirurile ordonate în mod natural și construiți matricea sufixelor din șiruri inversate, obținând prefixe în loc de sufixe.
adăugat autor Rafał Dowgird, sursa

Here's a WAG for you. I am in NO WAY Knuthian in my algorithm savvy

Okay, so the naiive Trie encodes string keys by starting at the root of the tree and moving down branches that match each letter in the key, starting at the first letter of the key. So the key "foo" would be mapped to (root)->f->fo->foo and the value would be stored in the location pointed to by the 'foo' node.

Căutați orice subreversă din cheie, nu doar substring-urile care încep de la începutul cheii.

Deci, ceea ce trebuie să faceți este să asociați un nod cu orice cheie care conține acel substring special. În exemplul pe care l-am dat înainte, NU ați fi găsit o referință la valoarea foo sub nodurile "f" și "fo". Într-un TST care acceptă tipul de căutări pe care vreți să faceți, nu veți găsi doar obiectul foo sub toate cele trei noduri ("f", "fo" și "foo"), l-ați găsi și el sub "o" și "oo", de asemenea.

Există câteva consecințe evidente pentru extinderea arborelui de căutare pentru a susține acest tip de indexare. În primul rând, tocmai ați explodat dimensiunea copacului. Zguduitor. Dacă îl puteți stoca și utiliza într-o manieră eficientă, căutările dvs. vor dura O (1). Dacă cheile dvs. rămân statice și puteți găsi o modalitate de a diviza indexul, astfel încât să nu luați o pedeapsă imensă de IO în utilizarea acestuia, acest lucru ar putea amortiza să fie în valoare de timp.

În al doilea rând, veți găsi că căutările pentru șiruri mici vor avea ca rezultat un număr mare de hit-uri, ceea ce ar putea face căutarea dvs. inutilă, dacă nu, de exemplu, ați pus o lungime minimă pe termenii de căutare.

On the bright side, you might also find that you can compress the tree via tokenization (like zip compression does) or by compressing nodes that don't branch down (i.e., if you have 'w'->'o'->'o'-> and the first 'o' doesn't branch, you can safely collapse it to 'w'->'oo'). Maybe even a wicked-ass hash could make things easier...

Oricum, WAG așa cum am spus.

2
adăugat
Nu este același lucru cu indicele de q-gram despre care vorbea Konrad?
adăugat autor Pacerier, sursa

/EDIT: Un prieten de-al meu mi-a arătat o ipoteză proastă în construirea mesei q-gram. Construcția poate fi mult mai simplă - și, prin urmare, mult mai rapidă. Am editat codul sursă și explicația pentru a reflecta acest lucru. Cred că ar putea fi soluția finală .

Inspirat de comentariul lui Rafał Dowgird la răspunsul meu anterior, mi-am actualizat codul. Cred că acest lucru merită un răspuns propriu, totuși, deoarece este și destul de lung. În loc de a umple corzile existente, acest cod construiește indicele peste matricea originală de șiruri de caractere. În loc să stocheze o singură poziție, matricea sufixelor stochează o pereche: indicele șirului țintă și poziția sufixului din acel șir. În rezultat, este necesar doar primul număr. Cu toate acestea, al doilea număr este necesar pentru construirea tabelului q -gram.

Noua versiune a algoritmului construiește tabelul q pentru a merge pe matricea sufixelor în locul șirurilor inițiale. Aceasta salvează căutarea binară a matricei sufixelor. În consecință, durata de execuție a construcției scade de la O ( n * log n ) până la O > n ) (unde n este dimensiunea matricei sufixelor).

Observați că, la fel ca prima mea soluție, folosirea SubString are ca rezultat o mulțime de copii inutile. Soluția evidentă este de a scrie o metodă de extensie care creează un ambalaj ușor în loc să copieze șirul. Comparația trebuie să fie ușor adaptată. Acest lucru este lăsat ca un exercițiu pentru cititor. ;-)

using Position = System.Collections.Generic.KeyValuePair;

class QGramIndex {
    private readonly int m_Q;
    private readonly IList m_Data;
    private Position[] m_SA;
    private Dictionary m_Dir;

    public QGramIndex(IList strings, int q) {
        m_Q = q;
        m_Data = strings;
        MakeSuffixArray();
        MakeIndex();
    }

    public int this[string s] { get { return FindInIndex(s); } }

    private int FindInIndex(string s) {
        int idx;
        if (!m_Dir.TryGetValue(s, out idx))
            return -1;
        return m_SA[idx].Key;
    }

    private void MakeSuffixArray() {
        int size = m_Data.Sum(str => str.Length < m_Q ? 0 : str.Length - m_Q + 1);
        m_SA = new Position[size];
        int pos = 0;
        for (int i = 0; i < m_Data.Count; ++i)
            for (int j = 0; j <= m_Data[i].Length - m_Q; ++j)
                m_SA[pos++] = new Position(i, j);

        Array.Sort(
            m_SA,
            (x, y) => string.CompareOrdinal(
                m_Data[x.Key].Substring(x.Value),
                m_Data[y.Key].Substring(y.Value)
            )
        );
    }

    private void MakeIndex() {
        m_Dir = new Dictionary(m_SA.Length);

       //Every q-gram is a prefix in the suffix table.
        for (int i = 0; i < m_SA.Length; ++i) {
            var pos = m_SA[i];
            m_Dir[m_Data[pos.Key].Substring(pos.Value, 5)] = i;
        }
    }
}

Utilizarea este aceeași ca în celălalt exemplu, minus argumentul maxlen necesar pentru constructor.

0
adăugat

Aveți avantajul de a avea cheile dvs. trie comparabile cu dimensiunea registrului mașinii? Deci, dacă sunteți pe o cutie de 32 de biți, puteți compara 4 caractere simultan în loc de fiecare caracter individual? Nu știu cât de rău ar crește dimensiunea aplicației.

0
adăugat

ar fi posibil să "hash" valoarea cheie? au în esență un al doilea arbore, toate valorile posibile pentru a căuta indicând o listă de chei în primul arbore.

Veți avea nevoie de 2 copaci; Prima este o valoare hash pentru obiectul de domeniu. al doilea arbore este șirul de căutare la valoarea hash. al doilea arbore are mai multe chei la aceeași valoare hash.

Example tree 1: STCKVRFLW -> domain object

tree 2: stack -> STCKVRFLW,STCK over -> STCKVRFLW, VRBRD, VR

Prin urmare, folosind căutarea pentru arborele 2 vă oferă o listă de chei pentru a căuta pe primul arbore.

0
adăugat

Alegeți o dimensiune minimă a șirului de căutare (de ex., Patru caractere). Treceți prin lista de intrări de coarde și construiți un dicționar al fiecărui substring de patru caractere, mapând la o listă de intrări în care apare subdistrul. Când efectuați o căutare, căutați în funcție de primele patru caractere ale șirului de căutare pentru a obține un set inițial, apoi restrânge setul inițial numai la cele care corespund șirului de căutare complet.

Cel mai rău caz este O (n), dar veți obține doar dacă intrările dvs. de coarde sunt aproape identice. Dicționarul de căutare poate fi destul de mare, deci este probabil o idee bună să îl stocați pe disc sau să utilizați o bază de date relațională :-)

0
adăugat

Pentru a interoga un set mare de text într-o manieră eficientă, puteți utiliza conceptul de Edit Distance/Prefix Edit Distance.

Editați distanța ED (x, y): numărul minim de transfromuri pentru a ajunge de la x la y

Dar calculul ED între fiecare termen și textul interogării este resurse și consumatoare de timp. Prin urmare, în loc de a calcula ED pentru fiecare termen, mai întâi putem extrage termenii de potrivire posibili utilizând o tehnică numită Index Qgram . și apoi să se aplice calculul ED pe acei termeni selectați.

Un avantaj al tehnicii indexului Qgram îl constituie suportul pentru Căutare fuzzy .

O posibilă abordare a adaptării indexului QGram este construirea unui index inversat folosind Qgrams. Aici stocăm toate cuvintele care constau în anumite Qgram (În loc să stocăm șir întreg, puteți utiliza un cod unic pentru fiecare șir).

col: col mbia, col col

Atunci când interogăm, calculăm numărul de Qgrams comune între textul interogării și termenii disponibili.

Example: x = HILLARY, y = HILARI(query term)
Qgrams
$$HILLARY$$ -> $$H, $HI, HIL, ILL, LLA, LAR, ARY, RY$, Y$$
$$HILARI$$ -> $$H, $HI, HIL, ILA, LAR, ARI, RI$, I$$
number of q-grams in common = 4

Pentru termenii cu număr mare de Qgrams comune, calculăm ED/PED în funcție de termenul de interogare și apoi sugerăm termenul pentru utilizatorul final.

you can find an implementation of this theory in following project. Feel free to ask any questions. https://github.com/Bhashitha-Gamage/City_Search

Pentru a afla mai multe despre distanța de editare, prefixul Editați distanța Qgram, vă rugăm să urmăriți următorul videoclip al Prof. Dr. Hannah Bast https://www.youtube.com/embed/6pUg2wmGJRo (Lecția începe de la 20:06 )

0
adăugat
SEO - optimizare, România & Moldova
SEO - optimizare, România & Moldova
120 participanți

Pentru confort, opriți notificările. Parteneri: ciupacabra.com Toate grupurile IT: @Grupuri_IT