[algoritme] mysql LIKE of MATCH AGAINST

[Explore]

Weet iemand waar ik het algoritme van mysql's 'LIKE' of 'MATCH AGAINST' kan vinden? Ik ben nl. op zoek naar een soort van fuzzy search en wat mysql doet is eigenlijk precies wat ik nodig heb.

De info die ik heb komt welliswaar uit een database, maar is, tegen de tijd dat het doorzocht wordt, al ingeladen in een servlet. Lijkt me nogal omslachtig om dan weer een query naar de DB te doen.

Momenteel heb ik een levenshtein-class, maar die zoekt niet goed genoeg.

Ik heb genoeg over fuzzy logic gezien. Allemaal blabla. Aan een stukje code, pseudo code of algoritme heb ik meer.

[TheDane]

hmm interesting ... ik heb op m'n werk nog een boek over fuzzy logic liggen,.

staat geloof ik wel wat in .. zal morgen wel eens kijken!

overigens, en misschien zit ik er wel helemaal naast, maar is mysql's LIKE search niet gewoon 'tzelfde als zoeken met wildcard ? valt dat onder de categorie "fuzzy" ?

[Nielsz]

Het is dus gewoon een string?


1. Je neemt de eerste letter van het woord dat je moet hebben.
2. Ga nu elke letter af in de string waarin je zoekt.
3. Doe dat totdat je de letter uit 1. heb gevonden.
4. neem de volgende letter uit het woord.
5. match die met de volgende letter uit de string.

bijvoorbeeld.

[bigtree]

Het eerste dat in me opkomt; bouw een functie die 2 woorden kan vergelijken en een score geeft hoe goed ze 'matchen'. Hoe beter ze machten, hoe hoger de score die de functie retourneert. Beter scoort: dezelfde letters in de dezelfde volgorde of dezelfde letters in de woorden.
Vervolgens kun je de mate van 'fuzzyness' instellen door alle woorden te retourneren die boven een bepaalde waarde scoren.

Bijv:
'bla' + 'blaa' = 75%
'bla' + 'bala' = 75%
'bla' + 'bal' = 80% (dezelfde letters, andere volgorde)

enzovoort

[Explore]

Dat zou ik niet weten. Maar ik heb wel de typische user input getest tegen de database met LIKE en ik kreeg precies terug wat ik wou zien...

Ik weet dat mysql open-source is, maaruh... Zal wel even zoeken zijn voordat ik het stuk code van LIKE gevonden heb.

[Explore]

Op maandag 03 juni 2002 00:13 schreef Nielsz het volgende:
Het is dus gewoon een string?

Ja. 2 om precies te zijn.

1. Je neemt de eerste letter van het woord dat je moet hebben.
2. Ga nu elke letter af in de string waarin je zoekt.
3. Doe dat totdat je de letter uit 1. heb gevonden.
4. neem de volgende letter uit het woord.
5. match die met de volgende letter uit de string.

Oke... Dit moet uitgebreid worden...

Als ik in 'abracadrabra' zoek naar 'drab' krijg ik zo een mooie hit terug (levenshtein levert hier een vrij slechte hit op, iets van 8 ofzo - hoe kleiner hoe beter). Maar als ik naar bv. 'draab' zou zoeken, wat dan? Geen hit? Afwijking van 1?

[Explore]

Op maandag 03 juni 2002 00:13 schreef bigtree het volgende:

Bijv:
'bla' + 'blaa' = 75%
'bla' + 'bala' = 75%
'bla' + 'bal' = 80% (dezelfde letters, andere volgorde)

enzovoort

Ja, bijvoorbeeld. Alleen hoe doe je dat?
Nielsz z'n voorbeeldje covert dit niet helemaal...

[Nielsz]

Op maandag 03 juni 2002 00:22 schreef Explore het volgende:

[..]

Ja, bijvoorbeeld. Alleen hoe doe je dat?
Nielsz z'n voorbeeldje covert dit niet helemaal...

vroeg je dat dan

[Verwijderd]

Wat je wil is een techniek om de jokertekens zoals '%' en '_' te matchen, het eenvoudigst is dit te implementeren met eindige deterministische automaten. Deze automaten stellen je reguliere expressie voor en elke toestand geeft aan hoe ver je expressie al is gematcht, en als je aan het eind van je automaat bent als je aan je alle tekens van een woord hebt gehad, dan ben je klaar.

Het probleem is echter om alle mogelijke paden die het woord oplevert voor de expressie te vinden. Dit worden er nogal veel. Het makkelijkste zou dus zijn om gebruik te maken van de reguliere expressies van PHP ofzo, als je het m.b.v. PHP uit de MySQL database haalt. Of welke taal je ervoor gebruikt.

Ik kan zo snel geen URL vinden waarop het goed wordt uitgelegd, maar wellicht dat je in een bibliotheek iets kan vinden, of je beter kan zoeken dan ik.

[Explore]

Ik hoorde iets over Tenary Search Trees (in tegenstelling tot Binary Search Trees). Is dat wat je bedoeld?

[drm]

Explore:
Tenary Search Trees

Ternary

[Explore]

Op maandag 03 juni 2002 09:58 schreef drm het volgende:

[..]

Ternary

Ja, typo. Die bedoel ik...
Maar dat is wat NemO bedoeld?

[drm]

Explore:
Maar dat is wat NemO bedoeld?

Geen idee eigenlijk Ik weet alleen hoe je het spelt

Maar hoe komt het dat je je data al in de servlet hebt, en het daarna nog eens wil doorzoeken Misschien moet je toch gewoon proberen om MySQL dat op te laten lossen


_{afgezien van het feit dat ik ook wel wil weten hoe zo'n fuzzy search in elkaar zit...}

[Explore]

Op maandag 03 juni 2002 11:17 schreef drm het volgende:

Geen idee eigenlijk Ik weet alleen hoe je het spelt

Maar hoe komt het dat je je data al in de servlet hebt, en het daarna nog eens wil doorzoeken Misschien moet je toch gewoon proberen om MySQL dat op te laten lossen

De data woont in een servlet, die bij initialisatie de database inleest en vervolgens zit te wachten op queries van de clients. Het lijkt me zo 'overkill' om de database weer aan te spreken, terwijl alle data al in een hashtable staat (of TST).

_{afgezien van het feit dat ik ook wel wil weten hoe zo'n fuzzy search in elkaar zit...}

Ja, ik ook. De resultaten die zo'n Fuzzy search teruggeeft zijn erg fijn. Ik denk dat ik zelf maar wat ga verzinnen, for the time being. 'k Heb weinig trek om in de code van mysql te gaan zoeken.

[Limhes]

kijk hier es, misschien dat je er wat aan hebt

[Explore]

Op dinsdag 04 juni 2002 11:39 schreef Limhes het volgende:
kijk hier es, misschien dat je er wat aan hebt

De NEC ResearchIndex had ik al gevonden. Alleen daar verdwaal ik in pagina's met links naar meer links naar meer links naar....... links! Niks concreets.

[Soultaker]

Op maandag 03 juni 2002 09:58 schreef drm het volgende:
Ternary

Ternaire zoekbomen.

Nu weet ik niet precies wat jullie onder een fuzzy algoritme verstaan, maar naar mijn mening betekent dit dat de stappen die doorlopen worden niet eenduidig worden vastgelegd door het soort problemen wat ermee opgelost wordt. Hierdoor kan de complexiteit van de verwerking van en de kwaliteit (en vorm) van oplossingen van gerelateerde problemen erg uiteenlopen. In die zin is een fuzzy algoritme te vergelijken met een heuristisch algoritme.

Het in MySQL gebruikte algoritme voor LIKE (en waarschijnlijk ook MATCH AGAINST, maar die ken ik niet), is eenduidig vastgesteld en volkomen 'logisch' (als in tegenstelling tot 'fuzzy'). Als je dat wilt begrijpen, hoef je eigenlijk alleen te zoeken naar parsers van reguliere expressie.

[Explore]

Op dinsdag 04 juni 2002 12:08 schreef Soultaker het volgende:

Het in MySQL gebruikte algoritme voor LIKE (en waarschijnlijk ook MATCH AGAINST, maar die ken ik niet), is eenduidig vastgesteld en volkomen 'logisch' (als in tegenstelling tot 'fuzzy'). Als je dat wilt begrijpen, hoef je eigenlijk alleen te zoeken naar parsers van reguliere expressie.

Je hebt helemaal gelijk. Mijn eerste testje was dit:

PHP:

<?    // Do a 'fuzzy' search for the key in the haystack    function fuzzySearch($key, $haystack) {                $results = array();                reset($haystack);        foreach ($haystack as $item) {            if (eregi($key,$item)) $results[] = $item;        }                return $results;    }?>

Welke dezelfde resultaten geeft als Mysql's LIKE.
Niks fuzzy's aan...

[Limhes]

maar wil je nou een echte fuzzy-search hebben of het algoritme voor LIKE? want dat laatste heb je dus blijkbaar al

[Explore]

Ik was op zoek naar een algoritme wat een fatsoenlijke match geeft voor een lijst namen/woorden. Ook als er maar een stuk van 't woord wordt ingetypt. Dat doet bovenstaande functie prima. Toen nog de typo's... Ik heb bovenstaande functie aangepast, zodat typo's ook goed matchen. En daar ben ik tevreden over.

Een complete fuzzy-search lijkt me nu niet meer nodig. We hadden al een TST draaien, maar dat is toch aanzienlijk complexer en zelfs minder flexibel dan de functie die ik nu zelf gebouwd heb. De TST was alleen in staat om prefixes te matchen. Dat is niet wat ik wil...