Come cercare frammenti di testo in un database

Question

Sono disponibili strumenti open source o commerciali che consentono l'indicizzazione del frammento di testo dei contenuti del database e possono essere interrogati da Java?

Sfondo della domanda è una grande tabella di database MySQL con diverse centinaia di migliaia di record, contenente diverse colonne VARCHAR. In queste colonne le persone vorrebbero cercare i frammenti dei contenuti, quindi un indice di testo completo (basato sui confini delle parole) non sarebbe di aiuto.

EDIT: [aggiunta di rendere chiaro il motivo per cui questi primi suggerimenti non risolverebbe il problema:]

Questo è il motivo di MySQL costruito nel indice full-text, non farà il lavoro, e nessuno dei due si Lucene o Sfinge, tutto di cui sono stati suggeriti nelle risposte. Ho già esaminato entrambi, ma per quanto posso dire, si basano sull'indicizzazione delle parole , escludendo le parole di arresto e facendo ogni sorta di cose sensibili per una vera ricerca a tutto campo. Tuttavia questo non è adatto, perché potrei essere alla ricerca di un termine di ricerca come "oison" che deve corrispondere a "Roisonic Street" e "Poison-Ivy". La differenza chiave qui è che il termine di ricerca è solo un frammento del contenuto della colonna, che non deve essere delimitato da caratteri speciali o spazi bianchi.

EDIT2: [aggiunta un po 'di informazioni di sfondo:] della funzione richiesta che deve essere attuata sulla base di questo è una ricerca molto allentato per le descrizioni degli oggetti in un sistema di gestione delle merci. Gli utenti spesso non conoscono il numero corretto dell'articolo, ma solo una parte del nome dell'articolo. Sfortunatamente la qualità di queste descrizioni è piuttosto bassa, provengono da un sistema legacy e non possono essere modificati facilmente. Se per esempio le persone cercavano un maglio, sarebbero entrati nella "slitta". Con un indice basato su parola/token questo non troverà corrispondenze che vengono memorizzate come "martello", ma solo quelle che ascoltano "slittaio". Ci sono tutti i tipi di strane varianze che devono essere coperte, rendendo impraticabile un approccio basato su token.

Attualmente l'unica cosa che possiamo fare è una query LIKE '%searchterm%', che disabilita in modo efficace qualsiasi utilizzo di indice e richiede molte risorse e tempo. Idealmente, qualsiasi strumento di questo tipo creerebbe un indice che mi permettesse di ottenere risultati per query simili molto rapidamente, così da poter implementare una ricerca simile a un riflettore, recuperando solo i dati "reali" dalla tabella MySQL tramite la chiave primaria quando un utente sceglie un record di risultati.

Se possibile, l'indice deve essere aggiornabile (senza richiedere una ricostruzione completa), poiché i dati potrebbero cambiare e dovrebbero essere disponibili per la ricerca immediatamente da altri client.

Sarei felice di ricevere consigli e/o rapporti di esperienza.

Edit3: soluzione commerciale ha rilevato che "solo funziona" Anche se ho avuto un sacco di buone risposte a questa domanda, ho voluto da notare qui, che alla fine siamo andati con un prodotto commerciale chiamato "QuickFind" , prodotto e venduto da un'azienda tedesca denominata "HMB Datentechnik". Si prega di notare che io sono non affiliato con loro in alcun modo, perché potrebbe apparire così quando andrò e descrivere ciò che il loro prodotto può fare. Sfortunatamente il loro website sembra piuttosto male ed è solo tedesco, ma il prodotto in sé è davvero eccezionale. Al momento ho una versione di prova da loro - dovrete contattarli, nessun download - e sono estremamente colpito.

Dato che non esiste una documentazione completa disponibile online, cercherò di descrivere le mie esperienze fino ad ora.

Quello che fanno è creare un file indice personalizzato basato sul contenuto del database. Possono integrarsi tramite ODBC, ma da quello che mi viene detto raramente i clienti lo fanno. Invece - e questo è quello che probabilmente faremo - genererai un'esportazione di testo (come CSV) dal tuo database principale e lo invierai al loro indicizzatore. Ciò consente di essere completamente indipendenti dalla struttura della tabella effettiva (o da qualsiasi database SQL); infatti esportiamo dati uniti da più tabelle. Gli indici possono essere aggiornati in modo incrementale in un secondo momento.

Sulla base del fatto che il loro server (solo 250kb circa, in esecuzione come app per console o servizio Windows) serve listener per query su una porta TCP. Il protocollo è basato sul testo e sembra un po '"vecchio", ma è semplice e funziona. Fondamentalmente si passa solo a quale degli indici disponibili si desidera interrogare e ai termini di ricerca (frammenti), delimitato dallo spazio. Sono disponibili tre formati di output, array HTML/JavaScript, XML o CSV. Attualmente sto lavorando su un wrapper Java per il protocollo un po 'datato. Ma i risultati sono fantastici: attualmente ho un set di dati di esempio di circa 500.000 record con 8 colonne indicizzate e la mia applicazione di test attiva una ricerca su tutte le 8 colonne per i contenuti di un JTextField su ogni sequenza di tasti durante la modifica e può aggiornare il visualizzazione dei risultati (JTable) in tempo reale! Questo accade senza passare all'istanza MySQL da cui originariamente provenivano i dati. Sulla base delle colonne che si ottengono, è possibile chiedere il record "originale" interrogando MySQL con la chiave primaria di quella riga (è necessario che sia inclusa nell'indice QuickFind, ovviamente).

L'indice rappresenta circa il 30-40% delle dimensioni della versione di esportazione del testo dei dati. L'indicizzazione era principalmente legata alla velocità di I/O del disco; i miei 500.000 record hanno richiesto circa un minuto o due per essere elaborati.

È difficile descriverlo perché ho trovato persino difficile da credere quando ho visto una demo di prodotto in-house. Presentarono un database di indirizzi di 10 milioni di righe e cercarono frammenti di nomi, indirizzi e numeri di telefono e quando si toccò il pulsante "Cerca", i risultati tornarono in meno di un secondo - il tutto fatto su un notebook! Da quello che mi è stato detto, spesso si integrano con i sistemi SAP o CRM per migliorare i tempi di ricerca quando gli agenti dei call center capiscono solo i frammenti dei nomi o degli indirizzi di un chiamante.

Quindi, in ogni caso, probabilmente non riuscirò a descriverlo. Se hai bisogno di qualcosa del genere, dovresti assolutamente controllare questo. Google Translate fa un lavoro abbastanza buono che traduce il loro sito web dal tedesco all'inglese, quindi questo potrebbe essere un buon inizio.

Answer 1

I haven Ho avuto questo specifico requisito da solo, ma la mia esperienza mi dice che Lucene può fare il trucco, anche se forse non da solo: lo userei sicuramente attraverso Solr come descritto da Michael Della Bitta in prima risposta Il link che ha dato era perfetto - leggilo per ulteriori informazioni.

In breve, Solr consente di definire i Tipi di campo personalizzati. Sono costituiti da un analizzatore Index-Time e un Analizzatore query-time.Gli analizzatori capiscono cosa fare con il testo e ciascuno di essi è costituito da un Tokenizer e da zero a molti TokenFilters. Tokenizer divide il testo in blocchi e quindi ogni TokenFilter può aggiungere, sottrarre o modificare i token.

Il campo può quindi finire per indicizzare qualcosa di molto diverso dal testo originale, inclusi più token, se necessario. Quindi quello che vuoi è una copia a più token del tuo testo originale, che tu chiedi inviando a Lucene qualcosa come "my_ngram_field: sledge". Non ci sono jolly coinvolti :-)

Poi si seguono un modello simile al prefisso ricerca offerto nel file solrconfig.xml:

<fieldType name="prefix_token" class="solr.TextField" positionIncrementGap="1"> 
    <analyzer type="index"> 
     <tokenizer class="solr.WhitespaceTokenizerFactory"/> 
     <filter class="solr.LowerCaseFilterFactory" /> 
     <filter class="solr.EdgeNGramFilterFactory" minGramSize="1" maxGramSize="20"/> 
    </analyzer> 
    <analyzer type="query"> 
     <tokenizer class="solr.WhitespaceTokenizerFactory"/> 
     <filter class="solr.LowerCaseFilterFactory" /> 
    </analyzer> 
</fieldType> 

L'EdgeNGramFilterFactory è il modo in cui implementare corrispondenza prefisso per casella di ricerca completamento automatico. Prende i token provenienti dalle fasi precedenti (singole parole delimitate da spazi bianchi trasformate in minuscole) e le fan in ogni sottostringa sul bordo principale. mazza = slitta, slitta, slitta, slitta, slitta, slitta, slitta ecc.

È necessario seguire questo schema, ma sostituire EdgeNGramFilterFactory con il proprio che fa tutti gli NGram nel campo. L'impostazione predefinita org.apache.solr.analysis.NGramFilterFactory è un buon inizio, ma trascrive le lettere per il controllo ortografico. Potresti copiarlo e spogliarlo - è una classe abbastanza semplice da implementare.

Una volta che avete il vostro FieldType (chiamarlo ngram_text) utilizzando il proprio MyNGramFilterFactory, basta creare il campo originale e il campo Ngram in questo modo:

<field name="title" type="text" indexed="true" stored="true"/> 
    <field name="title_ngrams" type="ngram_text" indexed="true" stored="false"/> 

Poi dire per copiare il campo originale nella fantasia uno:

<copyField source="title" dest="title_ngrams"/> 

Bene, ora quando si cerca "title_ngrams: slitta" si dovrebbe ottenere un elenco di documenti che contengono questo. Poi nella tua lista dei campi per la query devi solo dire di recuperare il campo chiamato titolo piuttosto che il campo title_ngrams.

Questo dovrebbe essere sufficiente per consentire di adattare le cose insieme e sintonizzarsi su livelli di prestazioni sorprendenti piuttosto facilmente. In un vecchio lavoro avevamo un database con oltre dieci milioni di prodotti con descrizioni HTML di grandi dimensioni e riuscivamo a convincere Lucene a fare sia la query standard che il controllo ortografico in meno di 200 ms su un server di medie dimensioni che gestiva diverse dozzine di query simultanee. Quando hai un sacco di utenti, il caching spara e fa gridare!

Oh, e l'indicizzazione incrementale (sebbene non in tempo reale) è un gioco da ragazzi. Può anche farlo sotto carichi elevati dal momento che crea e ottimizza il nuovo indice in background e lo scava automaticamente prima di cambiarlo. Molto lucido.

Buona fortuna!

Answer 2

Questo potrebbe non essere ciò che si desidera ascoltare, perché presumo che si stia tentando di risolverlo con codice SQL, ma Lucene sarebbe la mia prima scelta. È anche possibile costruire tecniche di classificazione e potenziamento abbastanza intelligenti con strumenti aggiuntivi. Lucene è scritto in Java, quindi dovrebbe darti esattamente l'interfaccia di cui hai bisogno.

Se eri un negozio Microsoft, la maggior parte di ciò che stai cercando è incorporato in SQL Server e puoi abilitare i caratteri jolly che ti daranno la possibilità di eseguire corrispondenze parziali di parole.

In Lucene e Lucene.Net, è possibile utilizzare wildcard matches se lo si desidera. Tuttavia, non è supportato l'utilizzo di caratteri jolly come primo simbolo in una ricerca. Se si desidera la possibilità di utilizzare i caratteri jolly del primo carattere, sarà probabilmente necessario implementare una sorta di indice basato su trie da solo, poiché in molti casi è un'operazione costosa per filtrare l'insieme di termini in qualcosa di ragionevole per il tipo di indice più comunemente necessario per le applicazioni di ricerca full text, in cui il suffix stemming è generalmente più prezioso.

È possibile modificare l'istanza di Query Parser in Lucene per sovrascrivere questa regola impostando setAllowLeadingWildcard su true.

Sono quasi sicuro che le ricerche con caratteri jolly su entrambe le estremità sono intrinsecamente inefficienti. Gli elenchi Salta sono talvolta usati per migliorare le prestazioni di tali ricerche con testo in chiaro, ma penso che sia più probabile trovare un'implementazione del genere in qualcosa come grep di uno strumento di indicizzazione del testo generalizzato.

Esistono altre soluzioni per il problema che si descrivono in cui una parola può essere digitata come due o viceversa. Le query fuzzy sono supportate in Lucene, ad esempio. Le varianti ortografica e morfologica possono essere gestite usando o fornendo un filtro che offre suggerimenti basati su una sorta di meccanismo bayesiano, o indicando trucchi, ovvero prendendo un corpus di varianti frequenti e inserendo l'indice in questi termini. Ho persino visto la conoscenza dei dati strutturati inseriti nel motore di testo completo (ad esempio aggiungendo il nome della città e la parola "hotel" ai record della tabella dell'hotel, per rendere più probabile che "Paris Hotels" includa un record per la pensione -house Caisse des Dépôts.) Anche se non è esattamente un problema banale, è gestibile senza distruggere i vantaggi delle ricerche basate su parole.

Answer 3

Sono sicuro che Mysql offre un'opzione fulltext e probabilmente è anche possibile utilizzare Lucene.

vedi qui per i commenti relativi

Best efficient way to make a fulltext search in MySQL

Answer 4

Se la tabella è MyISAM, è possibile utilizzare pieni capabilites di ricerca testo di MySQL: http://dev.mysql.com/doc/refman/5.0/en/fulltext-search.html

In caso contrario, il "standard" è http://www.sphinxsearch.com/

Alcune idee su cosa fare se si utilizza InnoDB: http://www.mysqlperformanceblog.com/2009/09/10/what-to-do-with-mysql-full-text-search-while-migrating-to-innodb/

Inoltre, una buona presentazione che introduce Sfinge e spiega l'architettura + utilizzo http://www.scribd.com/doc/2670976/Sphinx-High-Performance-Full-Text-Search-for-MySQL-Presentation

Aggiornamento
Dopo aver letto il vostro chiarimento alla domanda - Sfinge può fare sottostringa partite. Devi impostare "enable-star" e creare un indice infisso con il valore min_infix_length appropriato (1 ti darà tutte le sottostringhe possibili, ma ovviamente più alto è il set, più piccolo sarà l'indice e più velocemente le tue ricerche). Vedi http://sphinxsearch.com/docs/current.html per i dettagli.

Answer 5

Vorrei usare Apache Solr. La strategia di indicizzazione è completamente sintonizzabile (vedi http://wiki.apache.org/solr/AnalyzersTokenizersTokenFilters), può leggere in modo incrementale direttamente dal tuo database per popolare l'indice (vedi DataImportHandler nella stessa wiki), e può essere interrogato praticamente da qualsiasi linguaggio che parla HTTP e XML o qualcosa come JSON.

Answer 6

Quello che stai cercando di fare è improbabile che sia mai molto più veloce di LIKE '%searchterm%' senza una grande quantità di codice personalizzato. L'equivalente di LIKE 'searchterm%' dovrebbe essere banale però. Puoi fare quello che stai chiedendo costruendo un indice di tutte le parole parziali possibili che non sono coperte dalla wild-card finale, ma questo risulterebbe in una dimensione di indice incredibilmente grande, e sarebbe insolitamente lento per gli aggiornamenti. I token lunghi comporterebbero Bad Things ™. Posso chiedere perché è necessario questo? Ri: Spotlight ... Ti rendi conto che Spotlight non lo fa, giusto? È basato su token proprio come ogni altro indicizzatore full-text. Solitamente l'espansione della query è il metodo appropriato per ottenere corrispondenze inesatte se questo è il tuo obiettivo.

Edit:

ho avuto un progetto esattamente come questo a un certo punto; numeri di parte per tutti i tipi di cose. Alla fine abbiamo optato per lo searchterm* in Xapian, ma credo che Lucene abbia anche l'equivalente. Non troverai una buona soluzione che gestisca le ricerche con caratteri jolly su entrambi i lati del token, ma una wild card finale è in genere più che sufficiente per ciò che desideri, e sospetto che scoprirai che gli utenti si adattano al tuo sistema abbastanza rapidamente se hanno alcun controllo sulla pulizia dei dati. Combinalo con l'espansione delle query (o con l'espansione dei token limitata) e dovresti essere abbastanza ben impostato. L'espansione delle query converte una query per "martello" in "martello * OR (slitta * martello *)" o qualcosa di simile. Non tutte le query funzioneranno, ma le persone sono già abbastanza ben addestrate per provare le query correlate quando qualcosa non funziona, e fintanto che almeno una o due domande ovvie escogitano i risultati che si aspettano, dovresti essere a posto. La tua scommessa migliore è comunque quella di ripulire i dati e organizzarli meglio. Sareste sorpresi di quanto sia facile questo risultato se si esegue la versione di tutto e si implementa una politica di modifica egualitaria. Forse permettere alle persone di aggiungere parole chiave a una voce e assicurarsi di indicizzarle, ma porre dei limiti su quanti possono essere impostati. Troppi e potresti effettivamente degradare i risultati della ricerca.

Answer 7

cosa dire dell'utilizzo di strumenti come sopra proposto (lucene ecc.) Per l'indicizzazione di testo completo e la ricerca LIKE di casi in cui non è stato trovato nulla? (Esegui LIKE solo dopo che la ricerca indicizzata fulltext ha restituito risultati pari a zero)

Answer 8

La risposta esatta alla tua domanda è right here Se il rendimento sarà sufficientemente soddisfacente per la dimensione dei tuoi dati è un'altra domanda.

Answer 9

La ricerca di scandole potrebbe fare il trucco.

http://en.wikipedia.org/wiki/W-shingling

Ad esempio, se si utilizza l'herpes zoster 3 caratteri, è possibile dividere "Roisonic" a: "roi", "figlio", "IC", e memorizzare tutti i tre valori, associandoli originale iscrizione. Durante la ricerca di "oison", per prima cosa cercherete "ois", "iso", "son". Per prima cosa sfoglia tutte le voci di scandole (trovando quella con "figlio"), e poi puoi affinare la ricerca usando la corrispondenza esatta delle stringhe.

Si noti che l'assicella di 3 caratteri richiede che il frammento in query sia composto da almeno 5 caratteri, una tegola di 4 caratteri richiede una query di 7 caratteri e così via.

Answer 10

Un indice "reale" di testo completo che utilizza parti di una parola sarebbe molte volte più grande del testo di origine e mentre la ricerca potrebbe essere più veloce qualsiasi aggiornamento o elaborazione di inserimento sarebbe molto lento.

È unica speranza è se v'è una sorta di modello per il "errori made. Si potrebbe applicare una serie di 'regole di tipo IA' per il testo in ingresso e produrre sotto forma cannonical del testo, che si potrebbe poi applicare un indice di testo completo a. Un esempio per una regola potrebbe essere quello di dividere una parola che termina in martello in due parole s/(\ w?) (martello)/\ 1 \ 2/g o per cambiare "sledg" "slitta" e " schledge "to" sledge "Dovresti applicare lo stesso set di regole al testo della query.Nel modo in cui un prodotto descritto come" mazza "può essere abbinato alla ricerca di" sledg hammer "