Genera un'espressione regolare per una determinata stringa e modifica la distanza

Ho il problema che voglio far corrispondere tutte le stringhe nel database con una certa distanza di modifica a una determinata stringa.Genera un'espressione regolare per una determinata stringa e modifica la distanza

La mia idea era di generare un'espressione regolare che corrispondesse a tutte le stringhe con la distanza di modifica d nella stringa s.

Così, per esempio voglio generare una regex r per d = 1 e s = 'abc' sotto forma di: r = 'abc|.abc|.bc|a.c|ab.|abc.' e così via. Ma non sono sicuro se questo è molto efficiente o ci sono già alcuni buoni algoritmi per questo problema? Voglio considerare anche gli scambi di caratteri nella distanza di modifica. quindi r dovrebbe anche essere 'acb'. Voglio realizzarlo in PHP e quindi creare una query SQL: SELECT * FROM table WHERE name RLIKE TheRegularExpression.

È un buon modo per farlo in quel modo? O cosa consiglieresti?

fonte

2012-11-02 Martin Cup

Se si vuole l'efficienza, prima di tutto si dovrebbe evitare di applicare una condizione in cui che non può essere risolto utilizzando un indice per tutti i record in una tabella, a meno che il tavolo è abbastanza piccolo. – millimoose

Inoltre, considera che la lunghezza del pattern risultante sarà 'O (nCd)', dove 'n' è la lunghezza della stringa, e' d' è la tua distanza. Questo può potenzialmente portare a modelli molto grandi. Ad esempio, per una stringa di caratteri '80', con una distanza desiderata di '5', si invierà un RE di circa due gigabyte al database. (Questo è solo considerando le sostituzioni di caratteri, non le trasposizioni.) Tuttavia, se sei sicuro che le stringhe saranno corte e/o 'd' sia molto piccolo o molto vicino a' n', potrebbe essere fattibile. – millimoose

Un'altra implicazione è che se le stringhe vengono immesse dagli utenti, è necessario assicurarsi che la lunghezza sia entro un certo limite, altrimenti si creerebbe un buco DoS. (Come con qualsiasi algoritmo molto, molto inefficiente con parametri inseriti dall'utente.) – millimoose

Probabilmente la cosa migliore da fare è costruire un processo iterativo per tutte le possibilità. In altre parole, qualcosa di simile:

function findall($startString) { 
    // create an array of all strings that are distance one away 
    // each element would be $returnArray["abc"] = "abc"; 
} 

$d = 2; // distance 
$myArray[$startString] = $startString; 

for($i = 0; $i < $d; $i++) { 
    $newCombos = array_merge(array(), $myArray); 
    foreach($myArray as $element) { 
     $newCombos = array_merge($newCombos, findall($element)); 
    } 
    $myArray = array_merge(array(), $newCombos); 
} 

$myRegex = implode("|", $myArray);

fonte

2012-11-02 17:38:53 durron597

grazie! funziona come un fascino! –

l'unica cosa che ho notato della soluzione è che la query sql è molto lunga e lenta per parole più lunghe e una distanza di modifica superiore a 2. –

Penso che la soluzione della funzione Levenshtein sia probabilmente migliore della mia (di enrico.bacis) , Si dovrebbe controllare – durron597

È necessaria un'implementazione di Levenshtein Distance (o qualcosa di molto simile). Ecco uno function definition da utilizzare con MySQL.

fonte

2012-11-02 17:37:05 diolemo

Sarebbe probabilmente più efficiente modificare quell'algoritmo in modo che una determinata distanza di modifica superi la soglia richiesta, invece di calcolare inutilmente il risultato esatto. – millimoose

grazie. il problema è che sul server dove voglio usarlo non ho i diritti per usare le funzioni e le procedure memorizzate ... quindi devo implementarlo con php però ... –

È possibile memorizzare un Levenshtein function in Mysql. Dopo di che si può semplicemente fare la ricerca in questo modo:

mysql_qery("SELECT `term` FROM `words` WHERE levenshtein('$word', `term`) BETWEEN 0 AND '$d'");

fonte

2012-11-02 17:38:29

Genera un'espressione regolare per una determinata stringa e modifica la distanza

risposta

Problemi correlati