ricerca php (fuzzy) corrispondente a

Question

se qualcuno ha mai presentato una storia da digg, controlla se la storia è già stata presentata, presumo con una ricerca fuzzy.

Vorrei implementare qualcosa di simile e voglio sapere se stanno utilizzando una classe PHP che è open source?

Soundex isnt farlo, frasi/stringhe possono essere fino a 250chars di lunghezza

Answer 1

Si potrebbe (a seconda delle dimensioni del set di dati) usa ricerca full-text di MySQL, e cercare per la voce (s), che hanno un alto punteggio e si trovano entro un certo periodo di tempo e suggerire questo/questi all'utente.

Più di segnare qui: MySQL Fulltext Search Score Explained

Answer 2

Purtroppo, a far questo in PHP è proibitivo Tuttavia, si può certamente applicare l'algoritmo di piccoli insiemi di dati (ad alto utilizzo della CPU e della memoria.).

Per espandere in particolare su come è possibile creare un tracollo server: paio di funzioni built-in PHP determinerà "distanza" tra le stringhe: levenshtein e similar_text.

Dummy dati: (finta sono titoli di notizie)

$titles = <<< EOF 
Apple 
Apples 
Orange 
Oranges 
Banana 
EOF;
 

$titles = explode("\n", $titles);

A questo punto, $ titoli dovrebbe essere solo un array di stringhe. Ora crea una matrice e confronta ogni titolo con OGNI altro titolo per similarità. In altre parole, per 5 titoli, otterrai una matrice 5 x 5 (25 voci). Ecco dove entra la CPU e il memory sink.

Ecco perché questo metodo (tramite PHP) non può essere applicato a migliaia di voci. Ma se si voleva:

$matches = array(); 
foreach($titles as $title) { 
    $matches[$title] = array(); 
    foreach($titles as $compare_to) { 
     $matches[$title][$compare_to] = levenshtein($compare_to, $title); 
    } 
    asort($matches[$title], SORT_NUMERIC ); 
}

A questo punto quello che in fondo hai è una matrice con "distanze di testo." Nel concetto (non in dati reali) sembra un po 'come questa tabella qui sotto. Nota come c'è un insieme di valori 0 che vanno in diagonale - questo significa che nel ciclo di matching, due parole identiche sono - beh, identiche.

 
     Apple Apples Orange Oranges Banana 
Apple 0  1  5  6  6 
Apples 1  0  6  5  6 
Orange 5  6  0  1  5 
Oranges 6  5  1  0  5 
Banana 6  6  5  5  0 

Il $ reale corrisponde gamma si presenta un po 'come questo (troncato):

Array 
(
    [Apple] => Array 
     (
      [Apple] => 0 
      [Apples] => 1 
      [Orange] => 5 
      [Banana] => 6 
      [Oranges] => 6 
     ) 

    [Apples] => Array 
     (
     ... 

In ogni caso, è a voi (per la sperimentazione) determinare ciò che una buona distanza numerica cutoff potrebbe per lo più match - e poi applicarlo. Altrimenti, leggi su sphinx-search e usalo - dato che ha librerie PHP.

Orange sei contento di averlo chiesto?

Answer 3

Suggerirei di prendere gli URL inviati dagli utenti e di memorizzarli in più parti; nome di dominio, percorso e stringa di query. Usa la funzione PHP parse_url() per ricavare le parti dell'URL inviato.

Indicare almeno il nome del dominio e il percorso. Quindi, quando un nuovo utente invia l'URL, si cerca nel database un record corrispondente al dominio e al percorso. Dal momento che le colonne vengono indicizzate, verranno filtrati prima tutti i record che non si trovano nello stesso dominio e quindi cercando tra i record rimanenti. A seconda del set di dati, questo dovrebbe essere più veloce che semplicemente indicizzando l'intero URL. Assicurati che la tua clausola WHERE sia impostata nell'ordine corretto.

Se ciò non soddisfa le vostre esigenze, suggerirei di provare Sfinge. Sphinx è un motore di ricerca full text SQL open source che è molto più veloce della ricerca full-text di MySQL. Supporta lo stemming e alcune altre caratteristiche interessanti.

http://sphinxsearch.com/

Si potrebbe anche prendere il titolo o nel testo il contenuto della presentazione utenti, gestito attraverso una funzione per generare parole chiave, e la ricerca nel database per i record esistenti con quelli o parole chiave simili.