Dotaz: Hledání v databázi (slovník) nějakého výrazu či částečné podobnosti

[Bubla]

Dobrý den,

jakým způsobem se přistupuje ke hledání podobností v databázi? dejme tomu, že mám dotaz typu 'ahoj'

položky v databázi

- ahojblas - ahoj - blas - ldsd ahoj - bubak - kralik

jakým způsobem z tohoto seznamu poté vyfiltrovat slova, která mají největší podobnost? Celé toto hledání je spíše fulltext nebo fuzzy matching?

Předpokládám, že na tuto funkcionalitu budou potřebné regulární výrazy, že ano?

Odpovědi

[Bubla]

vzorek databáze ještě jednou

- ahojblas

- ahoj

- blas

- ldsd ahoj

- bubak

- kralik

[Tarmaq]

pokud ti staci jen vyrazy, ktere obsahuji 'ahoj', tak staci zadat:

SELECT vyraz
FROM vyrazy
WHERE vyraz LIKE '%ahoj%'

[potato]

Fuzzy matching se dělá v nejjednodušším případě Levenstheinovou vzdáleností řetězců s vhodně definovanými meziznakovými vzdálenostmi, ve složitějším s použitím statistických modelů daného jazyka. Což ovšem nenapíšeš standardním SQL dotazem. Nestandardní existují. Postgresql má přímo funkci levenshtein, dá se vygooglit jakási T-SQL implementace, etc.

Má-li záznam ten řetězec přímo obsahovat, nanejvýš s nějakým bordelem okolo, tak můžeš použít LIKE, jak píše kolega. Nicméně vybrat pak maximálně shodný zase potřebuje metriku nad řetězci, tudíž si tímhle moc nepomůžeš.

[Bubla]

děkuji za info

a jakým způsobem by se k tomuto přistupovalo, pokud by to bylo např. v programovacím jazyce místo SQL?

[DarkKnightCZ]

regularni vyrazy, pouzijes funkce stylu strstr/strpos, nebo si napises vlastni algoritmus stylem - "prochazej cely radek, znak po znaku, pokud se rovna aktualni znak prvnimu znaku slova a zaroven nasledujici znak se rovna druhemu znaku slova a zaroven dalsi nasledujici znak se rovna tretimu znaku slova atd. az po konec slova, slovo bylo nalezeno"

[potato]

Jen to ne. Najdeš si knihovnu, která implementuje řetězcové metriky, a použiješ ji. Hledej fuzzy matching, Levenshtein, string distance, edit distance, ...

[graviton]

http://norvig.com/spell-correct.html <- co třeba tohle, to je takový pěkný příklad...

[Bubla]

Děkuji, to vypadá jako pěkná ukázka, zkusím se z toho něco přiučit. Přitom se zkusím ještě podívat pořádně na ten fuzyy matching. ještě jednou děkuji za informace.

[Bubla]

tak tady je ještě další ukázka možností, kdyby někdo potřeboval

http://stackoverflow.com/questions/682367/good-python-modules-for-fuzzy-string-comparison

[Bubla]

a ještě obdobné vlákno na http://stackoverflow.com/questions/451884/similar-string-algorithm/451910#451910

[Bubla]

Tak to vypadá, že už mi něco funguje, teď jsem ale přišel na jeden zásadní problém...

jde totiž o to, že některé řetězce ze kterých bych chtěl vybírat, tak jsou různě dlouhé... např.

- 'Alfonz bulba velký'

- 'Quercus lodes malý'

- 'Sanchenzo Lopez'

- 'Lopez oglomenz'

- 'lodes'

a bohužel většina těch dostupných knihoven předpokládá celé jedno slovo, nebo sérii vůči sérii.

tedy pokud budu hledat 'lopez', tak s největší pravděpodobností vrátí 'lodes', a 'Lopez oglomenz' nebude mít dostatečně velký koeficient, napadlo mě tedy všechny rozdělit na části a hledat v nich, jenže to je pak nutné držet i původní verzi a nějak správně zacílit původní verzi. No další problém se vyskytne v případě kdy někdo zadá výraz 'lodes Sanchenzo' a já budu mít části rozdělené?

z toho mi vychází, že bude nutné provést několik testů a pak je mezi sebou porovnat? tedy rozdělit slova jak na vstupu tak v databázi a pak je opět nějak složit?

[potato]

To je otázka metriky. Já bych taky řekl, že lodes je bližší...

První krok asi tedy musí být pořádná specifikace kritéria blízkosti. Když máš dvě slova a jedno z nich odpovídá přesně, zjevně to preferuješ před přibližnou shodou podobně dlouhých slov. Co když budeš k tomu přesně odpovídajícímu slovu mít přilepenou celou větu? Bibli? Nekonečný rozvoj pí? Pořád to má být bližší než lodes? Nejdřív je nutné vědět, co chceš udělat, potom lze řešit jak.

[graviton]

Bez znalosti problémové domény asi těžko navrhneme přibližný trefovač, který by v ní generoval přirozeně se chovající odhady.

Jen nadhodím trik, se kterým jsme kdysi ubastlili relativně přirozeně se chovající slovníček nad daty s mixem slov a celých vět:

1. setřídili jsme si slovník podle délky slova/fráze vzestupně
2. hledání hledalo ve slovníku zadanou věc sekvenčně jako podřetězec (žádné překlepy)
3. hledání se zastavilo po N nálezech

Díky bodu 1 to přesné zásahy vracelo nejdřív a případně to potom vracelo i slova s daným podřetězcem nebo fráze s tím slovem.

Je otázka, jak do toho začlenit nějaké přibližné porovnávání, asi jet na dva průchody - přesný a přibližný, na výstupu jejich výsledky nějak ováhovaně zkombinovat.

Netuším, jestli z toho něco k něčemu bude, jen tak nadhazuju...

[Logik]

Asi to co chceš je, rozdělit si fráze ve slovníku po slovech a vrátit libovolnou, která má alespoň jedno slovo podobné. Popř. můžeš hodnotu podobnosti vydělit délkou fráze ve slovech.

Víceslovné fráze pak můžeš vyhledávat pomocí součinu podobnosti jednotlivých slov vyhledávané fráze.

[Bubla]

o to jsem se pokoušel, ale výsledek nebyl moc dobrý, jelikož se pak celé řetězce špatně skládaly dohromady.

nakonec jsem použil match slova na řetězec a v rozdělil několik úrovní pro "match" viz 0.0-1.0 např. SequenceMatcher pokud poté dosahuje určité úrovně, tak dojde k kontrole jednotlivých slov v řetězci a původního slova, pokud je nějaká vyšší úroveň, tak jí vrátí.

A tímto způsobem následně při hledání se vrátí několik matchu s různou úrovní přesnosti.