Struttura dati per la corrispondenza del testo "intuitivo"

Question

Struttura dati per la corrispondenza del testo "intuitivo"

#1 da (-1 voti)

2

Ho notato che gli editor di testo e simili hanno un algoritmo di corrispondenza dei pattern più-del-prefisso / suffisso che si svolge dietro le quinte. E l'algoritmo di corrispondenza dei tag di StackOverflow fa più di un semplice prefisso / suffisso corrispondente:

Mi chiedo quale sia (uno dei possibili molti tipi) di strutture dati per implementare questo tipo di funzionalità. Ho letto dei tentativi, ma sembrano essere migliori nella corrispondenza del prefisso e non sono del tutto sicuro del tipo di abbinamento in corso sul completamento automatico dei tag SO. Tuttavia, l'esame delle raccomandazioni sull'implementazione automatica di solito suggerisce i tentativi.

Chiedendosi se si potrebbe descrivere brevemente come è fatto. Sapere anche quali strutture dati o tipi di algoritmi sono chiamati aiuterebbe a cercare meglio i dettagli.

Questo è per stringhe relativamente piccole di dire meno di 1000 caratteri o forse meno di 200 se fa una differenza maggiore.

data-structures algorithms strings search

posta Lance Pollard 20.07.2018 - 14:53

fonte

1 risposta

Leggi altre domande sui tag data-structures algorithms strings search

Devo usare il framework junit Android nativo? Dove devo archiviare il file SQLite quando è condiviso tra un'applicazione web e una desktop?

score -1 · Answer 1

Il tuo esempio cerca corrispondenze esatte di un singolo pattern composto da personaggi successivi.

Se i tuoi elementi di testo sono in memoria, un approccio rapido sarebbe utilizzare una ricerca rapida con le stringhe usando ad esempio ricerca Boyer-Moore o sue varianti, per trovare gli articoli adatti. Più lungo è il modello, più efficiente diventa.

Se i tuoi elementi di testo sono su disco, è meglio usare l'indicizzazione di testo completo. Il tuo esempio riguarda le corrispondenze parziali in token elementari (cioè parole: un tag è solo una parola). Se il tuo database supporta funzioni avanzate di indicizzazione del testo, basta usarle (ad es. MongoDB , < a href="https://www.postgresql.org/docs/9.5/static/textsearch.html"> PostgreSql , SAP Hana ). Ma se no, un'alternativa facile potrebbe essere quella di costruire un indice di singole parole / token, che mappano le parole a tutti gli oggetti di testo in cui si verificano (relazione da molti a molti). Il tuo problema di autocompletamento sarebbe quindi ridotto a:

Ricerca di tutte le parole nel dizionario che corrispondono alla sottostringa
Ogni volta che i caratteri vengono aggiunti al pattern, si eliminano solo le corrispondenze sbagliate.
Naturalmente, trovare gli elementi di testo giusti non è sufficiente: dovrai ancora visualizzare queste voci ed evidenziare la parte rilevante: ecco di nuovo Boyer-More.