Autor Zpráva
DarkMeni
Profil
Zdravím, nevíte náhodou někdo, jak by měl vypadat algorytmus na vyhledávání podle vstupu od uživatele v dlouhých řetězcích na nalezení výsledku (řetězce), který by měl minimálně 40% shody a nějak vypočítat, kolik % shody tam je aby se to potom dalo nějak seřadit?

Například:
Když mám třeba:
$řetězce = array(
  'abcd efgah ijk lmno',
  'cdef lmnopq rstuv',
  'slovo slovo2',
  'slovó',
  'další slovo, třeba slovo3',
  //...
  'dlouhý řetězec...'
);
Když zadám "abcd", aby to našlo [0]
Když zadám "slovó", aby to našlo a seřadilo [3] [2] [4]
Když zadám "slovo2" aby to našlo a seřadilo jako [2] [4] [3] (tu 2 u slovo"2" by vzal jako překlep, protože je to hodně podobný, ale co se víc podobá by mělo větší pripritu)
A když tam dám "acbd" tak zase [0] i přes ten překlep (podobnost mi připadá větší než 40%)

Jestli jsem dobře popsal, co chci, je nějaká už zabudovaná funkce v php na porovnání 2 řetězců a rozpoznání, jak moc si jsou podobný? Nebo napadá někoho nějakej algorytmus na toto? Google to nějak umí, i přes tolik dat co má, porovnávat docela rychle, takže buď má efektivní algorytmus nebo na to má jinej jazyk, kterej to s řetězci umí.
Alphard
Profil
PHP má soundex() ten ale pro dlouhé stringy moc nepomůže.
A ve slově algoritmus píšeme i.
DarkMeni
Profil
Díky, zkusim, co to umí. Prej vrací první písmeno a čísla (ale co znamenaj?), slovo soundex (jestli s tím maj něco společnýho) mi nic neříká.
A jo jasně :D, nějak sem si to spojoval s rytmem, dám si na to bacha, díky.
Chamurappi
Profil
Reaguji na DarkMeniho:
Nebo napadá někoho nějakej algorytmus na toto? Google to nějak umí, i přes tolik dat co má, porovnávat docela rychle
Google to má vymyšlené tak, že sleduje sekvenci toho, co lidi hledají a z ní se učí. Pokud třeba hodně lidí hledalo „algorytmus“ a pak se opravilo na „algoritmus“, usoudí z toho, že „algorytmus“ je pravděpodobně špatně zapsaným algoritmem. Díky tomu dokáže správně pochopit i hodně divné věci, jako je třeba „w525*ed5e“, což je „wikipedie“ napsaná na notebookové klávesnici se zapnutým numlockem.

Potíž je, že takto stavěná funkce potřebuje k rozumnému fungování opravdu značné množství uživatelů.
Jinak konstrukčně to bude nejspíš heštabulka (asociativní pole), tam asi nejde vymyslet nic světobornějšího.
DarkMeni
Profil
Aha, tak takle to google dělá, díky.
peta
Profil
1. slovo2 // presna shoda
2. slovo? || slov?2 || slo?o2 || sl?vo2 || s?ovo2 || ?lovo2 // 1 znak
3. slov?? || slo??2 || sl??o2 || s??vo2 || ??ovo2 + dalsi kombinace (?slov?) // 2 znaky
Ale, jak se to pise do mysql nebo php, to bych musel chvili vymyslet.
SeparateSK
Profil
Ja by som to riešil pomocou similar_text(); a hladania toho najpodobnejšieho textu v poli
Tento urobí to,že ak zadáš napr "devať", tak to poopraví na "deväť".
$pole=array("deväť","žíhľava","pŕhľava");
function zisti_podobne($vstup,$pole,$minPodobnost){
   $vstup=strtoupper($vstup);  
    $nahrad=Array("Á","Ä","Č","Ď","É","Í","Ĺ","Ľ","Ň","Ó","Ô","Ŕ","Ř","Š","Ť","Ú","Ů","Ý","Ž");
    $scim=Array("A","A","C","D","E","I","L","L","N","O","O","R","R","S","T","U","U","Y","Z");
    $vstup=str_replace($nahrad,$scim,$vstup);
    $vstup=strtolower($vstup);
    $novePole=array();
    $percent=0;
    $text=0;
    $max=0;
    for($i=0;$i<count($pole);$i++){
        $novePole[]=strtolower(str_replace($nahrad,$scim,strtoupper($pole[$i])));
        similar_text($vstup,$novePole[$i],$percent);
        if($percent>$minPodobnost){
            if($percent>$max){
                $max=$percent;
                $text=$i;
            }
        }
    }
    if($max>0)return $pole[$text];
        else return false;
}
echo "Mali ste namysli: ".zisti_podobne("zih?ava",$pole,60)."?"; 
DarkMeni
Profil
Jasně, tu se sice odstraňuje diakritika, takže by pak "plast" a "plášť" měly stejnou prioritu i kdyby si někdo dal tu práci a napsal slovo "plášť" s diakritikou, a naopak to samí. Ale tenhle kód vypadá dobře, zkusim ho, díky. Jen nebudu porovnávat slovo se slovem, ale jedno až víc slov s docela dlouhými řetězci, tak snad je na tom similar_text s rychlostí docela dobře.

Vaše odpověď

Mohlo by se hodit


Prosím používejte diakritiku a interpunkci.

Ochrana proti spamu. Napište prosím číslo dvě-sta čtyřicet-sedm: