javascript - texto - Búsqueda de frases parciales múltiples para que una frase original no pueda coincidir con varias frases de búsqueda
funcion para buscar en javascript (4)
Dado un conjunto predefinido de frases, me gustaría realizar una búsqueda basada en la consulta del usuario. Por ejemplo, considere el siguiente conjunto de frases:
index phrase
-----------------------------------------
0 Stack Overflow
1 Math Overflow
2 Super User
3 Webmasters
4 Electrical Engineering
5 Programming Jokes
6 Programming Puzzles
7 Geographic Information Systems
El comportamiento esperado es:
query result
------------------------------------------------------------------------
s Stack Overflow, Super User, Geographic Information Systems
web Webmasters
over Stack Overflow, Math Overflow
super u Super User
user s Super User
e e Electrical Engineering
p Programming Jokes, Programming Puzzles
p p Programming Puzzles
Para implementar este comportamiento usé un trie . Cada nodo en el trie tiene una matriz de índices (vacíos inicialmente).
Para insertar una frase en el trie, primero la rompo en palabras. Por ejemplo, Programming Puzzles tiene index = 6 . Por lo tanto, agrego 6 a todos los siguientes nodos:
p
pr
pro
prog
progr
progra
program
programm
programmi
programmin
programming
pu
puz
puzz
puzzl
puzzle
puzzles
El problema es que cuando busco el prog p consulta, primero obtengo una lista de índices para prog que es [5, 6] . Luego, obtengo una lista de índices para p que también es [5, 6] . Finalmente, calculo la intersección entre los dos, y devuelvo el resultado [5, 6] , que obviamente está mal (debería ser [6] ).
¿Cómo arreglarías esto?
Observación clave
Podemos usar el hecho de que dos palabras en una consulta pueden coincidir con la misma palabra en una frase solo si una palabra de consulta es un prefijo de la otra palabra de consulta (o si son las mismas). Entonces, si procesamos las palabras de la consulta en orden descendente lexicográfico (los prefijos vienen después de sus "superpalabras"), entonces podemos eliminar con seguridad las palabras de las frases en la primera coincidencia. Al hacerlo, no dejamos posibilidad de unir la misma palabra de frase dos veces. Como dije, es seguro porque los prefijos coinciden con el superíndice de las palabras de la frase lo que sus "superpalabras" pueden coincidir, y el par de palabras de consulta, donde una no es un prefijo de la otra, siempre coincide con un conjunto disjunto de palabras de frase.
No tenemos que eliminar palabras de frases o trie "físicamente", podemos hacerlo "virtualmente".
Implementación del algoritmo
var PhraseSearch = function () {
var Trie = function () {
this.phraseWordCount = {};
this.children = {};
};
Trie.prototype.addPhraseWord = function (phrase, word) {
if (word !== '''') {
var first = word.charAt(0);
if (!this.children.hasOwnProperty(first)) {
this.children[first] = new Trie();
}
var rest = word.substring(1);
this.children[first].addPhraseWord(phrase, rest);
}
if (!this.phraseWordCount.hasOwnProperty(phrase)) {
this.phraseWordCount[phrase] = 0;
}
this.phraseWordCount[phrase]++;
};
Trie.prototype.getPhraseWordCount = function (prefix) {
if (prefix !== '''') {
var first = prefix.charAt(0);
if (this.children.hasOwnProperty(first)) {
var rest = prefix.substring(1);
return this.children[first].getPhraseWordCount(rest);
} else {
return {};
}
} else {
return this.phraseWordCount;
}
}
this.trie = new Trie();
}
PhraseSearch.prototype.addPhrase = function (phrase) {
var words = phrase.trim().toLowerCase().split(//s+/);
words.forEach(function (word) {
this.trie.addPhraseWord(phrase, word);
}, this);
}
PhraseSearch.prototype.search = function (query) {
var answer = {};
var phraseWordCount = this.trie.getPhraseWordCount('''');
for (var phrase in phraseWordCount) {
if (phraseWordCount.hasOwnProperty(phrase)) {
answer[phrase] = true;
}
}
var prefixes = query.trim().toLowerCase().split(//s+/);
prefixes.sort();
prefixes.reverse();
var prevPrefix = '''';
var superprefixCount = 0;
prefixes.forEach(function (prefix) {
if (prevPrefix.indexOf(prefix) !== 0) {
superprefixCount = 0;
}
phraseWordCount = this.trie.getPhraseWordCount(prefix);
function phraseMatchedWordCount(phrase) {
return phraseWordCount.hasOwnProperty(phrase) ? phraseWordCount[phrase] - superprefixCount : 0;
}
for (var phrase in answer) {
if (answer.hasOwnProperty(phrase) && phraseMatchedWordCount(phrase) < 1) {
delete answer[phrase];
}
}
prevPrefix = prefix;
superprefixCount++;
}, this);
return Object.keys(answer);
}
function test() {
var phraseSearch = new PhraseSearch();
var phrases = [
'''',
''Math Overflow'',
''Super User'',
''Webmasters'',
''Electrical Engineering'',
''Programming Jokes'',
''Programming Puzzles'',
''Geographic Information Systems''
];
phrases.forEach(phraseSearch.addPhrase, phraseSearch);
var queries = {
''s'': '', Super User, Geographic Information Systems'',
''web'': ''Webmasters'',
''over'': '', Math Overflow'',
''super u'': ''Super User'',
''user s'': ''Super User'',
''e e'': ''Electrical Engineering'',
''p'': ''Programming Jokes, Programming Puzzles'',
''p p'': ''Programming Puzzles''
};
for(var query in queries) {
if (queries.hasOwnProperty(query)) {
var expected = queries[query];
var actual = phraseSearch.search(query).join('', '');
console.log(''query: '' + query);
console.log(''expected: '' + expected);
console.log(''actual: '' + actual);
}
}
}
Uno puede probar este código aquí: http://ideone.com/RJgj6p
Posibles optimizaciones
Almacenar el recuento de palabras de frase en cada nodo trie no es muy eficiente en cuanto a la memoria. Pero al implementar trie comprimido es posible reducir la peor complejidad de memoria de caso a O (nm) , n es el número de palabras diferentes en todas las frases, ym es el número total de frases.
Para simplificar, inicializo la
answeragregando todas las frases. Pero un enfoque más eficiente con el tiempo consiste en inicializar laansweragregando las frases que coinciden con la palabra de consulta que coincide con el número mínimo de frases. A continuación, interseca con las frases de la palabra de consulta que coincidan con el segundo número mínimo de frases. Y así...
Diferencias relevantes de la implementación a la que se hace referencia en la pregunta
- En el nodo I, almaceno no solo las referencias de frase (ids) que coinciden con la subestación, sino también el número de palabras coincidentes en estas frases. Por lo tanto, el resultado del emparejamiento no es solo las referencias de frase coincidentes, sino también el número de palabras coincidentes en estas frases.
- Proceso palabras de consulta en orden descendente lexicográfico.
- Restamos el número de superprefixes (palabras de consulta de las cuales la palabra de consulta actual es un prefijo) de los resultados de coincidencia actuales (mediante el uso de variable
superprefixCount), y una frase se considera emparejada por la palabra de consulta actual solo cuando el número resultante de palabras coincidentes en es mayor que cero Al igual que en la implementación original, el resultado final es la intersección de las frases coincidentes.
Como se puede ver, los cambios son mínimos y las complejidades asintóticas (tanto del tiempo como de la memoria) no se modifican.
Después de pensarlo, se me ocurrió una idea similar a la de dened''s: además del índice de una frase coincidente, cada prefijo se referirá a cuántas palabras es un prefijo en esa frase, entonces ese número se puede reducir en el proceso de consulta por el número de sus superfixes entre otras palabras de consulta, y los resultados devueltos incluyen solo aquellos con al menos el mismo número de palabras coincidentes que la consulta.
Podemos implementar un pequeño ajuste adicional para evitar grandes controles cruzados al agregar (para el idioma inglés) un máximo de aproximadamente 26, elija 2 + 26, elija 3 e incluso 26 adicionales elijan 4 elementos especiales para el trie que se refieran a los pedidos primero. intersecciones de letras. Cuando se inserta una frase, los elementos especiales en el trie que se refieren a las combinaciones de primera y segunda letras recibirán su índice. Luego, los resultados del emparejamiento de las palabras de consulta más grandes se pueden cotejar con estos. Por ejemplo, si nuestra consulta es " Geo i ", los resultados de coincidencia para "Geo" se compararán con el elemento especial trie, "gi" , que con suerte tendría significativamente menos resultados de coincidencia que "i" .
Además, dependiendo de las circunstancias específicas, las comprobaciones cruzadas grandes a veces podrían manejarse más eficientemente en paralelo (por ejemplo, a través de un conjunto de bits &).
Puede resolverlo como un problema de correspondencia de gráficos en un gráfico bipartito .
Para cada documento, el par de consultas define el gráfico:
G=(V,E) Where
V = {t1 | for each term t1 in the query} U { t2 | for each term t2 in the document}
E = { (t1,t2) | t1 is a match for t2 }
Intuitivamente: tiene un vértice para cada término en la consulta, un vértice para cada término en el documento y una ventaja entre un término de documento y un término de consulta, solo si el término de consulta coincide con el término del documento. Ya has resuelto esta parte con tu trie.
Obtuviste un gráfico bipartito, solo hay bordes entre los "vértices de consulta" y los "vértices del documento" (y no entre dos vértices del mismo tipo).
Ahora, invoque un problema coincidente para el gráfico bipartito , y obtenga una coincidencia óptima {(t1_1,t2_1), ... , (t1_k,t2_k)} .
Su algoritmo debe devolver un documento d para una consulta q con m términos en la consulta, si (y solo si) se cumplen todos los términos m , lo que significa que tiene coincidencia máxima donde k=m .
En su ejemplo, el gráfico para query = "prog p", y document = "Programming Jokes", obtendrá el gráfico bipartito con la coincidencia: (o con Programming, p matching - no importa cuál)
Y, para la misma consulta, y document = "Puzzles de programación", obtendrá el gráfico bipartito con el correspondiente:
Como puede ver, para el primer ejemplo, no hay correspondencia que cubra todos los términos, y "rechazará" el documento. Para el segundo ejemplo, pudo hacer coincidir todos los términos y lo devolverá.
Para problemas de rendimiento, puede hacer el algoritmo sugerido solo en un subconjunto de frases, que ya fueron filtradas por su enfoque inicial (intersección de documentos que tienen coincidencias para todos los términos).
Si el conjunto de frases está definido y no contiene frases largas, quizás pueda crear no 1 trie, sino n tries, donde n es la cantidad máxima de palabras en una frase.
En i-th trie tienda i-th palabra de la frase. Vamos a llamarlo el trie con la etiqueta ''i''.
Para procesar la consulta con m palabras, consideremos el siguiente algoritmo:
- Para cada frase almacenaremos la etiqueta más baja de un trie, donde se encontró la palabra de esta frase. Denominémoslo como d [j], donde j es el índice de frase. Al principio para cada frase j, d [j] = -1.
- Busque la primera palabra en cada uno de los n intentos.
- Para cada frase j, encuentre la etiqueta de un trie que sea mayor que d [j] y donde se encuentre la palabra de esta frase. Si hay varias etiquetas de ese tipo, elija la más pequeña. Denotemos una etiqueta como c [j].
- Si no hay tal índice, esta frase no puede ser igualada. Puede marcar este caso con d [j] = n + 1.
- Si hay tal c [j] que c [j]> d [j], entonces asigne d [j] = c [j].
- Repita para cada palabra que quede.
- Todas las frases con -1 <d [j] <n coinciden.
Esto no es muy óptimo. Para mejorar el rendimiento, debe almacenar solo los valores utilizables de d array. Después de la primera palabra, almacene solo frases, emparejadas con esta palabra. Además, en lugar de la asignación d [j] = n + 1, elimine el índice j. Procese solo índices de frases ya almacenados.