Mi piacerebbe scoprire come la ricerca lucene funzioni così velocemente. Non riesco a trovare documenti utili sul Web. Se hai qualcosa (a parte il codice sorgente di lucene) da leggere, fammi sapere.Come funziona Lucene
Una query di ricerca di testo utilizzando la ricerca di testo mysql5 con indice richiede circa 18 minuti nel mio caso. Una ricerca lucene per la stessa query richiede meno di un secondo.
Lucene è un indice invertito di testo completo. Ciò significa che prende tutti i documenti, li divide in parole e quindi costruisce un indice per ogni parola. Poiché l'indice è una stringa esatta, non ordinata, può essere estremamente veloce. Ipoteticamente, un indice SQL non ordinato su un campo varchar potrebbe essere altrettanto veloce, e infatti penso che i grandi database possano fare una semplice query di parità di stringa molto rapidamente in quel caso.
Lucene non deve ottimizzare per l'elaborazione delle transazioni. Quando aggiungi un documento, non è necessario assicurarsi che le query lo vedano all'istante. E non ha bisogno di ottimizzare per gli aggiornamenti ai documenti esistenti.
Tuttavia, alla fine della giornata, se si vuole veramente sapere, è necessario leggere la fonte. Entrambe le cose a cui fai riferimento sono open source, dopotutto.
Se ho capito bene, ciò che distingue i motori di ricerca del testo è il modo in cui gestiscono le ricerche in più parole e unendo i risultati delle ricerche a più indici in tempo reale. Non consiglierei di consultare la fonte di Lucene per questo.Probabilmente sarebbe meglio leggere un po 'sulla teoria della ricerca testuale, la risposta di @ alienCoder mi ha aiutato. –
@bmargulies, Se l'indicizzazione è "per parola", allora perché la ricerca utente stackoverflow http://stackoverflow.com/users consente le corrispondenze di sottostringa? – Pacerier
Questo non è il posto per le risposte di un libro intero. Ci sono un certo numero di elaborazioni sul concetto di base in là. – bmargulies
In una parola: indicizzazione.
Lucene crea un indice del documento che consente di effettuare ricerche molto più rapidamente.
È la stessa differenza tra una struttura di dati O (N) dell'elenco e una struttura dati O (1) della tabella hash. L'elenco deve percorrere l'intera collezione per trovare ciò che desideri. La tabella hash ha un indice che consente di capire esattamente dove si trova l'oggetto desiderato e semplicemente di recuperarlo.
Update: "Ricerche indice Lucene sono molto più veloce di ricerche di indice mysql"
Io non sono certo cosa si intende per
La mia ipotesi è che tu stia usando MySQL "WHERE documento LIKE '% frase%'" per cercare un documento. Se è vero, MySQL deve eseguire una scansione tabella su ogni riga, che sarà O (N).
Lucene può analizzare il documento in token, raggrupparli in n-grammi verso la propria direzione e calcolare indici per ognuno di essi. È O (1) per trovare una parola in un documento Lucene indicizzato.
Sì, comprendo la parte di indicizzazione, ma ancora una volta, le ricerche dell'indice di lucene sono molto più veloci delle ricerche dell'indice mysql. Come succede? – Midhat
Lucene crea un grande indice. L'indice contiene la parola id, il numero di documenti in cui la parola è presente e la posizione della parola in quei documenti. Pertanto, quando si esegue una query con una sola parola, viene eseguita una ricerca nell'indice (complessità temporale O (1)). Quindi il risultato viene classificato utilizzando diversi algoritmi. Per la query con più parole, prendi semplicemente l'intersezione dell'insieme di file in cui sono presenti le parole. Quindi Lucene è molto molto veloce.
Per maggiori informazioni leggere questo articolo di Google developers- http://infolab.stanford.edu/~backrub/google.html
Scremato su quel foglio, è stato piuttosto utile. Nello specifico, "4.5 Ricerca" aveva la risposta che stavo cercando. In particolare, sembra che una ricerca di hash O (1) venga utilizzata per singole parole, ma una scansione O (n) viene utilizzata per unire i risultati con un limite di 40.000 documenti. Presumo che un algoritmo di riduzione della mappa sia usato per suddividere questo lavoro in modo che l'utente ottenga risultati istantanei. –
Un algoritmo popolare è l'algoritmo del rango di piccione. Anche se non ne so molto. – alienCoder
Quella carta è divertente: "In questo documento, presentiamo Google, un prototipo ...". Immagino che Google non sia sempre stata una mega-corporation. – Buttons840
Posso chiedere a questa domanda per essere convertito in un wiki comunità? Lucene suona come una piattaforma ora. – asyncwait