Algoritmo per trovare le unità di massima corrispondenza

Suggerirei anche di pre-elaborare il tuo database in un trie e di estendere il commento corrispondente dato da Christophe:

Dai un'occhiata all ' algoritmo di Aho-Corasick per la costruzione di un tale trie. L'idea generale è di avere una struttura dati ad albero che puoi seguire.

Nel tuo caso, consideriamo che hai anche la voce del database A B C E . Inizi a esaminare il trie con A (perché è il primo carattere della stringa di query). Esiste un tale nodo, perché i tuoi modelli validi includono A B e A B C E . Poi guardi il prossimo carattere della tua query, B , e trova una prima corrispondenza completa A B . Dal momento che hai bisogno del più lungo, vorrai continuare, naturalmente. Il nodo che hai raggiunto tramite A B è anche lo stesso nodo che continua a formare A B C E . Quindi continui con C e poi quando vuoi continuare con D non hai pattern validi con un prefisso di A B C D a sinistra.

Primo: puoi ripetere questo processo a partire da B e così via per ogni lettera della tua query. Questo ti darà la risposta corretta attraverso il massimo finale sulla lunghezza di tutti i modelli trovati. Non è molto efficiente, dal momento che puoi immaginare di eseguire più volte le stesse sottostringhe.

Inserisci la magia dei link di scelta rapida: il tuo trie contiene un nodo che rappresenta il prefisso A B C (dal modello A B C E ) e la tua query corrisponde a quel prefisso. Saprai quindi che la query meno il% co_de esaurito inizia con A . Sai anche in anticipo che B C ha B C D E come prefisso. Quindi al tuo trie può essere assegnata una scorciatoia dal nodo B C al nodo A B C . Non è necessario ricominciare da capo, ma puoi continuare direttamente con B C dalla tua query. E poi D e hai abbinato E . Poiché non c'è più corrispondenza per B C D E disponibile, devi risciacquare e ripetere.

Anche in questo caso, la scorciatoia dal nodo F al nodo B C D E consente di riconoscere C D E entro altri due passaggi. A questo punto hai scoperto C D E F G , A B e B C D E mentre guardi solo i caratteri di input C D E F G una volta.

Per completezza, dopo aver abbinato A B C D E F G , salteresti direttamente a C D E F G corrispondente. Dato che la tua migliore scorciatoia disponibile (con le parole di esempio limitate che hai dato) è F G - non c'è nulla che inizi con F G e niente che inizi con D E F G , quindi E F G è la tua migliore scommessa e il collegamento punta a quel nodo .

Nota speciale: potrebbe essere necessario prestare particolare attenzione a riconoscere le parole sotto-modello. Ad esempio, considera il database contenente F G e A B C D E F G e il tuo input è C D E . Finirai nel nodo A B C D E F H e non avrai più scorciatoie disponibili, quindi inizierai dall'inizio con A B C D E F , ma nel frattempo dovrai occuparti di aver abbinato H .

Questo approccio, tuttavia, richiede di pre-elaborare l'intero database in anticipo. Sul lato positivo, si ottengono ricerche lineari molto veloci (lineari in diversi parametri - è possibile leggere i dettagli sulla pagina wikipedia collegata).

In MySQL 5.6 ...

create table tt (
  data varchar(20)
 );

insert into tt values ('B C D E');
insert into tt values ('A B');
insert into tt values ('F G');
insert into tt values ('C D E F G');

insert into tt values ('X');

insert into tt values ('E D C B');
insert into tt values ('B A');
insert into tt values ('G F');
insert into tt values ('G F E D C');

select data,length(data) from tt where 'A B C D E F G' rlike data;


|      data | length(data) |
|-----------|--------------|
|   B C D E |            7 |
|       A B |            3 |
|       F G |            3 |
| C D E F G |            9 |

Aggiunta query per conteggiare il numero massimo di spazi (e quindi il numero massimo di unità corrispondenti)

select data,max(length(data)-length(replace(data,' ',''))+1) num_units_matched
from tt
where 'A B C X D E F G' rlike data
group by data
order by 2 desc
limit 1;

|      data | num_units_matched |
|-----------|-------------------| 
|       A B |                 2 |

Basandosi su ciò che @Frank ha scritto, ho provato a fare un resoconto dell'abbinamento con il dizionario trie.

La prima colonna mostra la stringa di input letta finora (ed elaborata). Il secondo mostra tutte le posizioni parziali corrispondenti nel trie. Il terzo mostra le partite di maggior successo.

Ad ogni iterazione, il successivo carattere di input viene catenato su ognuna delle posizioni parziali abbinate dalla precedente iterazione e usato per cercare le corrispondenze del trie. Il carattere di input corrente viene anche utilizzato indipendentemente per cercare le corrispondenze del trie (come se il carattere di input fosse catenato su una stringa vuota).

Stringa di input da abbinare: ABCDEFGH

Dizionario (che è trasformato in un trie per la ricerca)

(1) A
(2) ABC
(3) BC
(4) BCD
(5) BCDE
(6) CD
(7) CDE
(8) CDEF
(9) CDEFG

Input String   Positions of partial matches in the Trie             Longest matches
============   =================================================    ===============
A              A->(1,2)
AB             AB->(2) ; B->(3,4,5)
ABC            ABC->(2); BC->(3,4,5); C->(6,7,8,9)
ABCD           ABCD->(Stop); BCD->(4,5); CD->(6,7,8,9); D->(Stop)   ABC
ABCDE          BCDE->(5), CDE->(7,8,9); E->(Stop)
ABCDEF         BCDEF->(Stop); CDEF->(8,9); F->(Stop)                BCDE
ABCDEFG        CDEFG->(8); G->(Stop)
ABCDEFGH       CDEFGH->(Stop); H->(Stop)                            CDEFG