Dezvoltarea de algoritm de căutare neclare bazat pe Publicarea Hash în revista „tânăr om de știință“
Scopul acestei lucrări este de a dezvolta un algoritm optim pentru cautare fuzzy, baze de date dicționar.
În cursul lucrărilor a fost realizat un algoritm de căutare bazat pe un hash. Metrica primar, care a fost folosit pentru a compara siruri de caractere - Levenshtein distanță. Acest algoritm ar trebui să fie suficient de eficient pentru a reduce timpul de căutare ca Levinstein valoare are complexitate pătratică.
Cuvinte cheie: cautare fuzzy, Levinstein distanta, hașura
Probleme generale de căutare fuzzy.
Sub cautare fuzzy inseamna cuvinte cheie de căutare, luând în considerare eventualele erori aleatoare în scrierea cuvântului cheie sau, dimpotrivă, greșeli de ortografie în interogarea țintă.
Punctul-cheie de a construi o cercetare competentă este alegerea unei măsuri de similitudine între cuvinte sau, așa cum sunt numite, funcția de distanța dintre cuvinte, pe care o numim metrica.
Un alt aspect important este corect elementele de indexare pentru căutare rapidă și de încredere. Folosiți cuvinte suficient de consumatoare de comparație valori de funcționare, prin urmare, este necesar să se aloce un subset al dicționarului inițial care poate conține elemente de interogarea de căutare.
Alegerea cuvintelor compararea valorilor.
Cel mai frecvent este o metrica Lowenstein metrice. Levinstein distanța - este cea mai mică distanță de editare, astfel încât o linie merge la alta. Această valoare este foarte popular și utilizate pe scară largă, așa că nu vom insista pe ea în detaliu.
În cazul liniilor de comparație este preferabil să se calculeze o distanță pentru fiecare cuvânt separat, mai degrabă decât pentru întregul rând. Mai mult decât atât, este necesar să se efectueze normalizare pentru a evalua cuvinte coeficient de similaritate. În cazul nostru, acest raport va fi calculat cu următoarea formulă:
,
unde d (S1 (i), S2 (i)) Levenshtein distanță, n - numărul de cuvinte într-un rând (de obicei, Lang n = 3); S1, S2 constă dintr-o secvență de cuvinte, asa ca am calcula Levenshtein distanta pentru fiecare pereche de cuvinte; k - arată similitudinea a două secvențe de cuvinte (două SIF).
Metoda de indexare de vocabular.
Calcularea distanței Levenshtein are o complexitate pătratică, de aceea este foarte important să selectați dicționarul în setul inițial, care ar conține interogarea inițială. Metode similare se bazează pe eșantionare, t. e. Alocarea elementelor caracteristice ale rândurilor. Metoda cea mai potrivită pentru baze de date mici (mii până la 500.000. Elemente Vocabulary) este hash semnăturii [1]. Această abordare oferă cea mai bună combinație de căutare de calitate și viteza de procesare de interogare. Acesta are avantajul față de alte metode, cum ar fi soundex (Metafonie), n-grame, căutare copac, deoarece permite să facă greșeli în orice parte a cuvântului de căutare și, astfel, calitatea nu este degradat. Acest lucru este esențial atunci când traducerea numelor românești în alfabetul latin. Mai mult decât atât, o astfel de metodă de accelerare de căutare pentru orice limbă. Un exemplu de o astfel de funcție poate fi. Această funcție a fost sugerată în [5]. Această caracteristică este foarte potrivit pentru a citi dicționarul cu spațiu pe disc, dar din moment ce, în acest caz, întregul dicționar este încărcat în memorie, opțiunea cea mai adecvată ar fi următoarea formulă :, u (i) - un element de dicționar, k = lungimea (u (i) ). Însumăm toate valorile unice ale șirului de caractere și de a obține o anumită imagine. Astfel, vom construi o cartografiere surjectiv a elementelor dicționarului într-un set de imagini și vectorul coloană primit, unde n - dimensiunea dicționarului
Descrierea algoritmului utilizat, și compararea rezultatelor.
Algoritmul de căutare va fi pus în aplicare după cum urmează:
- Dicționar sortate după valori ascendente h (i) - valori hash
- Û (1): în cazul în care y - cererea de intrare a imaginii
- k = koeff (u (i), a), - se calculează coeficienții de similaritate; dacă găsiți elemente cu k = 1,0, căutarea este completă.
- û (2) = t = max (octeți (char)) - valoarea maximă a simbolului codului
și așa mai departe. Expand eșantion submulțime am limitat numărul de ori egal cu numărul maxim admisibil de inserare eroare sau ștergere. Variabila t la fiecare pas crește, adică. E. La început ne uităm la un imagini cu potrivire exactă (t = 0 * t), denumit în continuare t = t * 1 și căutați pentru elementul din set (fără elementele celui anterior) și așa mai departe, extinderea maximă de mai multe ori.
Folosind această metodă de indexare și folosind Levinstein metrice, puteți obține următoarele rezultate. Figura prezintă o comparație între viteza de căutare și indexare, fără a utiliza metoda de indexare propusă în lucrarea noastră. Pentru acuratețea rezultatelor folosite de intrare set de 20 elemente (20 cereri pentru fiecare dimensiune a dicționarului) și momentul în care a fost măsurat.
Fig. 1 Costurile timp de comparare pentru căutarea convențională și hașura căutare
Vedem că, odată cu creșterea în mărime a dicționarului, câștigătoare devine esențială. Mai mult decât atât, în exemplul considerat un caz în care dicționarul nu conține solicitarea necesară și eroarea admisibilă 3. În căutarea situației reale, algoritmul propus va dura mult mai puțin timp.
Acum, compara algoritmi de căutare utilizând funcțiile hash de la intrarea Boytsova LM [5] și utilizat în funcțiune (în comparație cu situația în care ia în considerare elementul nu este în eroare dicționar 3 și admisă, setul de intrare include 20 de cereri).
Fig. 2 Compararea de căutare consumatoare de timp, folosind funcția Boytsova și articolul propus
Bazat pe grafic, vedem că metoda noastră a arătat cele mai bune rezultate. Mai mult decât atât, algoritmul a fost implementat într-o bază de date locală și folosite cu succes. Acesta oferă un motor de căutare rapid fulger.
Termeni de bază (generate automat). cautare fuzzy, Levinstein distanta, algoritmul unei cautare fuzzy, algoritmul de căutare, dicționarul elementele Levinstein dicționar dimensiunea metrice, problemele de cautare fuzzy, metoda de regăsire neclare, comparandu cuvinte, comparând-consumatoare de timp, metoda de indexare comparație șir dicționar, o multitudine de metode dicționar elemente de accelerare căutarea, construirea de căutare competente subset dicționar inițială, dezvoltarea unui algoritm fuzzy algoritm fuzzy, costuri optime de căutare temporare.