javascript - placa - g expresiones regulares

¿Cómo hacer coincidir y resaltar todos los términos en cualquier orden de una serie de cadenas? (5)

Actualización 2

Abandonó el concepto de reducir el tamaño del conjunto debido a problemas con la restauración de las cadenas de trabajo en Vue.

Ahora, el método es simplemente el siguiente:

Preprocese el conjunto de opciones para mantener la pantalla sincronizada con el trabajo.
Procesar los términos.
Reduzca (filtre) la opción establecida iterando sobre ella y repitiendo los términos, cortocircuitando cuando hay una falta de coincidencia.
Usando el conjunto reducido, iterando sobre cada opción, encuentra los rangos de coincidencia.
Inserte cadenas HTML alrededor de cada rango de coincidencia.

El código está comentado.

Raw javascript (registra la matriz de opciones filtrada / manipulada): https://jsfiddle.net/pvLj9uxe/14/

Nueva implementación de Vue: https://jsfiddle.net/15prcpxn/30/

El cálculo parece razonablemente rápido: la actualización de DOM es lo que lo mata.

Añadido a la comparación *: https://jsfiddle.net/ektyx133/4/

* Advertencia: el preprocesamiento de las opciones (tratadas como "estáticas") forma parte de la estrategia, por lo que se ha procesado fuera del índice de referencia.

Antiguo intento

https://jsfiddle.net/15prcpxn/25/

Mi intento es usar Vue para renderizar (los métodos son secuenciales, por lo que probablemente pueda ponerlo todo en una función monolítica sin mucho esfuerzo; las entradas serán términos y conjunto de opciones completo; los conjuntos de opciones se filtrarán y los intervalos resaltados).

Dividir la entrada en términos individuales
Ordene los términos por longitud (primero el término más largo, de modo que cuando tenga una opción como "abc ab", y los términos "a abc", es decir, un término sea una subcadena de otro término, pueda coincidir "abc")
Copiar / cambiar términos a minúsculas
Opciones de copia (nuestro "conjunto de visualización") en minúsculas (nuestro "conjunto de trabajo")
Para cada término, elimine las opciones de trabajo sin coincidencias del "conjunto de trabajo" y, en paralelo, elimine las opciones de visualización del "conjunto de visualización"; al hacerlo, elimine las cadenas de términos coincidentes de las cadenas de opciones de trabajo supervivientes, por ejemplo, coincida con el término "a"en la opción "abc"cede "bc" [la implementación real es la inversa: para cada término, vuelva a crear "conjunto de trabajo" cuando haya coincidencias, y en paralelo agregue opciones de visualización al "conjunto de visualización", luego pase estos conjuntos al siguiente término] - esto nos da el filtro conjunto de pantalla
Copie el conjunto de visualización filtrada en minúsculas, para obtener un nuevo conjunto de trabajo filtrado
Para cada opción de trabajo en el conjunto de trabajo filtrado restante, cree un conjunto de rangos, registrando los rangos (es decir, el inicio y el final, por ejemplo, el término coincidente "a"en la opción "abc":) start = 0, end = 1donde cada término coincide tomando el desplazamiento (inicio) de la coincidencia y el duración del término / partido. Reemplace la cadena coincidente con espacios vacíos (u otro carácter no utilizado) de igual longitud que el término y agregue esto al siguiente término, por ejemplo, término coincidente "a"en los "abc"rendimientos de las opciones " bc": esto preserva la longitud de la opción de trabajo, asegurando que el conjunto de trabajo filtrado ( en minúsculas) coincide con el conjunto de pantalla filtrada (estuche original). El número total de conjuntos de rango será igual al número de opciones restantes en el conjunto de opciones filtradas.
Además, ordene los rangos dentro de cada conjunto de rangos (en orden descendente, para trabajar en sentido inverso), para permitir la inserción de cadenas.
Para cada opción en el conjunto de visualización se filtró (de trabajo en sentido inverso a fin de no perturbar el índice cuando la manipulación de la cadena), insertar las <u> </u>etiquetas alrededor de los rangos emparejados por cortado de la opción de visualización, por ejemplo búsqueda de término "a"en la opción "abc":new option = "<u>" + "a" + "</u>" + "bc"
Hazlo

El rendimiento es deficiente cuando hay muchas coincidencias / términos no útiles (por ejemplo, cuando ingresa un solo carácter). Para uso final, probablemente pondría en un retraso de cálculo de entrada.

Debería poder resumir algunos de estos pasos en menos pasos que puedan mejorar el rendimiento. Mañana volveré a visitar.

Es de suponer que Vue también se encarga de algunas de las optimizaciones a través de DOM virtual, etc., por lo que no necesariamente reflejará la representación vainilla de Javascript / DOM.

Los requisitos son:

Encuentre cadenas de una matriz (desde aquí en las opciones llamadas) que incluyen TODOS los términos en CUALQUIER orden
Resalte correctamente los términos coincidentes, es decir, inserte una cadena antes y después de cada término coincidente. Estoy usando <u> y </u> aquí
Tanto la consulta de búsqueda como las opciones pueden ser "cualquier cosa"

En aras de la simplicidad, las respuestas pueden concentrarse en la búsqueda sin distinción de mayúsculas y minúsculas en una lista que incluye solo caracteres ASCII y suponer que el término delimitador es un espacio simple, es decir. una consulta ingresada como "Foo bar baz" significa que los términos de búsqueda son [''foo'', ''bar'', ''baz''] .

Para aclarar:

Todos los términos deben existir por separado en las opciones coincidentes, es decir, los términos más cortos no deben existir solo como subcadenas de los términos más largos y no deben solaparse dos términos
Los términos de búsqueda repetidos deben existir en la opción al menos tantas veces como en la consulta

La aplicación final es (quizás no sorprendentemente) un autocompletado de clases.

TL; DR
El violín más reciente comparando los algoritmos propuestos de lado a lado:
https://jsfiddle.net/Mikk3lRo/ndeuqn02/7/
(No dude en actualizar este enlace si agrega un nuevo algoritmo)
jsPerf compara los algoritmos de una manera un poco más realista / representativa: algunas cadenas son básicamente "ingresadas" un carácter a la vez en cada repetición:
https://jsperf.com/comparison-of-algorithms-to-search-and-highlight
En este punto, está claro (gracias a la excelente comparación de bases de Trincot) que la mayor parte del tiempo utilizado por las implementaciones originales se gastó en la salida de DOM. Su importancia se ha minimizado tanto como sea posible en el violín.
Todavía hay una clara diferencia en el rendimiento entre los algoritmos en cada búsqueda, pero ninguno de ellos es tan rápido en cada pulsación de tecla. Después de revisar y limpiar mi propio "Dividir y Conquistar", supera a los demás de manera consistente en cualquier escenario realista que intente.
Tigregalis introdujo la idea de una optimización previa a la ejecución, que parece razonable dado que es poco probable que las opciones cambien entre pulsaciones de teclas. He añadido (una función para) esto a todos los métodos aquí. El único algoritmo en el que vi un beneficio obvio fue en las Permutaciones de Skirtle, pero animaré a cada persona que conteste a considerar si podría ser útil para sus propios algoritmos.
Algunos algoritmos serán mucho más fáciles de adaptar que otros. Todavía opino que esto será más importante que las pequeñas diferencias de rendimiento en una implementación real.
Tenga en cuenta que la versión actual del Conjunto de encogimiento de Tigregalis tiene un error: lo he excluido de fiddle y jsperf hasta que se solucione.

Permutaciones virales

En teoría, esto se puede resolver "manualmente" construyendo un RegExp que contenga cada posible permutación de los términos de búsqueda separados por un grupo de captura para capturar cualquier cosa entre los términos: una búsqueda de "foo bar" da como resultado (foo)(.*?)(bar)|(bar)(.*?)(foo) .

El resaltado se realiza en una sola pasada con string.replace() . Si hay algún cambio en la cadena tenemos una coincidencia.

Manifestación:

<input type="text" id="viral_permutations" onkeyup="viral_permutations()"> <p id="viral_permutations_meta"></p> <pre style="width:100%;overflow:auto;background:#eee" id="viral_permutations_regex"></pre> <ul style="height:300px;overflow:auto" id="viral_permutations_result"></ul>

Gracias a Trincot por señalar que mi versión original ocasionalmente resaltaría un término recurrente dos veces, lo cual se corrige en este fragmento.

Falla porque:

La expresión regular crece exponencialmente a medida que se agregan los términos. A los 7 términos (incluso letras individuales) pasaron los 250 kb y mi navegador se da por vencido con un Error: regexp too big ...

Algunas otras estrategias notables que no funcionaron:

Capturando grupos con todos los términos en cada grupo:

(foo|bar)(.*)(foo|bar)

Falla porque:

Coincidirá con las opciones que incluyen términos repetidos - fx. The food in the food court coincidiría aunque obviamente no debería.
Si "verificamos" que todos los términos fueron, de hecho, se encontró que fallará para encontrar coincidencias válidas - fx. The food in the food bar encontraría foo dos veces y nunca llegaría al bar .

Lookaheads negativos y referencias inversas:

(foo|bar|baz)(.*?)((?!/1)(?:foo|bar|baz))(.*?)((?!/1|/3)(?:foo|bar|baz))

Falla porque:

Cada vez que se repitan los términos en la consulta, se alcanzarán condiciones imposibles como "Find me a foo , bar o bar que no es foo ni a bar ".
Estoy bastante seguro de que tiene otros problemas, pero dejé de perseguirlo cuando me di cuenta de que tenía fallas lógicas.

Lookaheads positivos

(?=.*foo)(?=.*bar)(?=.*baz)

Falla porque:

Es muy difícil (si no imposible) resaltar de manera confiable las coincidencias encontradas.
No he encontrado ninguna manera de asegurar que todos los términos realmente existan, es decir. todos pueden estar presentes individualmente en la opción, pero los términos más cortos solo pueden existir como subcadenas de términos más largos, o los términos pueden superponerse.

Divide y conquistaras

Algo más complicado que la estrategia de Permutaciones virales de regex único : este algoritmo recursivo busca cada término uno tras otro, comenzando con el más largo.

Cada vez que se encuentra una coincidencia, se divide esa "mordida" en tres (a menos que al principio o al final), se marque la "mordida" combinada como consumida e intenta coincidir con el siguiente período más largo en cualquiera de las "picaduras" no consumidas.

Cuando no puede encontrar el término no coincidente más largo, retrocederá e intentará coincidir con el término anterior en una posición diferente (incluso en una "mordida" diferente).

Si regresa al más largo plazo y no puede encontrar otra posición para que coincida, se devolverá falso.

Esto significa que en la mayoría de los casos puede devolver las no coincidencias con bastante rapidez, simplemente porque ni siquiera contienen el plazo más largo.

Por supuesto si se queda sin términos - es decir. coincide exitosamente con el más corto - devolverá el partido resaltado uniendo de nuevo todas las "picadas".

Manifestación:

Actualizado para mejorar el rendimiento : el algoritmo base es exactamente el mismo, pero hubo algunas llamadas bastante caras arr.slice()que podrían evitarse por completo.

<input type="text" id="divide_and_conquer" onkeyup="divide_and_conquer()"> <p id="divide_and_conquer_meta"></p> <ul style="height:300px;overflow:auto" id="divide_and_conquer_result"></ul>

Esta estrategia presenta problemas de rendimiento cuando la consulta consta exclusivamente de cadenas (generalmente muy cortas) que están todas / las más presentes en muchas de las opciones, como aaaaaaaa...

En escenarios realistas, actualmente está superando a los otros algoritmos propuestos; consulte el enlace a jsperf agregado a la pregunta.

Lo intenté, pero no estoy seguro de cuánta ayuda será. Mi enfoque es similar a tu técnica de Dividir y Conquistar.

En lugar de cortar bits de la cadena, busco cada término antes de tiempo y almaceno una colección de todos los partidos, registrando las posiciones de inicio y finalización. Si no hay suficientes coincidencias para un término de búsqueda en particular, el algoritmo salta inmediatamente para esa "opción".

Una vez que ha reunido todas las coincidencias posibles, intenta recursivamente encontrar una combinación que no se superponga. Hay mucha copia de estructuras de datos en esa recursión y sospecho que podría optimizarse mucho mejor de lo que tengo aquí. También puedo solo disculparme por algunos de los nombres de las variables, estaba luchando para encontrar nombres que tuvieran algún sentido en absoluto.

Para ciertas búsquedas de prueba, como anananan ... parece que se las arregla mejor que la técnica original de Dividir y Conquistar, pero sospecho que puede ser solo por el rescate temprano que se realiza cuando se encuentran coincidencias insuficientes para un término de búsqueda en particular . Sin una gran cantidad de datos reales, es difícil saber dónde se encuentran las optimizaciones realmente valiosas.

<h1>Permutations</h1> <input type="text" id="search" onkeyup="search()" autocomplete="off"> <p id="terms"></p> <p id="time"></p> <ul id="results"></ul>

Actualizar:

Basado en los comentarios de Mikk3lRo en los comentarios, he hecho un poco de ajuste de rendimiento y he encontrado esto:

https://jsfiddle.net/skirtle/ndeuqn02/1/

El algoritmo central es el mismo, pero lo he hecho mucho más difícil de entender, todo en nombre del rendimiento. La mayoría de los cambios se relacionan con evitar la creación de nuevos objetos siempre que sea posible.

Como el algoritmo realiza una gran búsqueda por adelantado de cosas que nunca podría necesitar, siempre habrá oportunidades para que otros algoritmos sean más rápidos, especialmente en casos simples. Muchos de esos casos podrían manejarse por separado, pero no he intentado ese tipo de optimización.

En Chrome, ahora supera a las otras implementaciones en muchos escenarios diferentes, aunque es una comparación injusta ya que aún no se han ajustado de la misma manera. Las otras implementaciones tienden a ser un poco más rápidas en Firefox para búsquedas simples, pero los tiempos están todos en el mismo campo de juego.

Algunas búsquedas particularmente interesantes:

a ab ba baba . Agregué una nueva ''opción'' y ajusté el CSS para demostrar esto. Los algoritmos difieren en la forma elegida para realizar el resaltado. Mi algoritmo favorece el orden de los términos en la consulta en lugar de basarlo en la longitud de los términos. Hay otras optimizaciones disponibles si no me preocupo por el pedido, pero creo que solo ayudarían en casos extremos de solapamientos.
tristandacunha Tenga en cuenta los espacios entre las letras, estos son 14 términos de búsqueda separados. Si escribe este término a la vez, Dividir y Conquistar comenzará rápidamente a luchar, pero se recuperará hacia el final. Limpie y la Sombra se las arregla bien durante más tiempo, pero cuando escribe la letra c , se caerán de un precipicio. Creo que es una explosión exponencial en el retroceso, pero no lo he confirmado. Estoy seguro de que con un poco de trabajo podría tratarse en casos simples, pero podría ser más difícil de solucionar en los casos en que el retroceso se debe a una superposición sin solución.

Estoy seguro de que todas las implementaciones podrían acelerarse con un poco más de ajuste y unos pocos bits de manejo de casos especiales cuidadosamente diseñados. Cuál es realmente el "mejor" para los escenarios reales, no estoy seguro, pero mi opinión actual es que mi algoritmo probablemente solo tenga un punto estrecho en el que superaría a los demás en una prueba realmente justa. Un algoritmo que no hace todo lo que la búsqueda por adelantado parece difícil de superar para las búsquedas reales.

Actualización 2

He intentado una implementación diferente de mi enfoque anterior:

https://jsfiddle.net/skirtle/ndeuqn02/9/

Tenga en cuenta que solo he actualizado mi propia implementación, las otras están desactualizadas.

Pensé que intentaría evitar búsquedas innecesarias al realizarlas perezosamente en lugar de hacerlas todas por adelantado. Todavía los almacena en caché para que puedan reutilizarse si el algoritmo necesita retroceder. No sé si esto hace una diferencia significativa, ya que realizar pequeñas cantidades de búsquedas adicionales en cadenas cortas probablemente no suponía una gran sobrecarga.

También experimenté con recortar la función recursiva. Si bien parece que funciona, creo que hay un alto riesgo de errores (necesitaría muchas pruebas unitarias para asegurarse de que realmente funciona). No estoy convencido de que esta parte fue realmente un éxito porque las estructuras de datos involucradas hacen que sea realmente difícil de seguir. Parece ser rápido pero no lo suficiente como para justificar la complejidad.

También experimenté con formas alternativas para construir los aspectos más destacados finales. Toda esa clasificación y corte parece ser una pérdida de rendimiento, pero, nuevamente, el código se complica al tratar de evitarlo. Sin embargo, algunas de estas ganancias podrían ser aplicables a los otros algoritmos.

Otra idea que he presentado aquí es un análisis previo a la búsqueda de los términos de la consulta (depende solo de la consulta y no de las opciones). Comprueba si los términos pueden superponerse y para cualquier término en el que una superposición sea imposible (por ejemplo, cat dog ) utiliza un algoritmo mucho más simple para agarrar las coincidencias. Esta idea también podría aplicarse a los otros algoritmos.

Como se mencionó en los comentarios, la idea de ejecutar algún tipo de análisis previo a la búsqueda de las opciones también es posible, pero en realidad no lo he implementado aquí. Es difícil saber qué tipo de índice de búsqueda sería más beneficioso, ya que depende de cosas como el uso de la memoria y los detalles de las opciones. Sin embargo, podría ser más práctico tratar de transferir pequeñas cantidades de información de una búsqueda a la siguiente.

Por ejemplo, si alguien busca united states hay una buena probabilidad de que lo último que escribieron fue la última s y que su búsqueda anterior fuera un united state . Dos posibles optimizaciones basadas en esto son:

Las opciones de coincidencia para united states serán un subconjunto de aquellas para united state , por lo tanto, si recordamos esa lista, podríamos evitar tener que revisar todas las demás opciones. Esto podría ser usado para cualquiera de los algoritmos.
En el caso de mi algoritmo, las memorias caché de coincidencia podrían conservarse de una búsqueda a la siguiente. Si bien la entrada de caché para el state no sería de ninguna utilidad, la entrada para united sería exactamente la misma de una búsqueda a la siguiente, lo que nos permite omitir una parte costosa del algoritmo para ese término.

Yo sugeriría una ligera variante de la idea de dividir y conquistar: en lugar de dividir la cadena en trozos (mordidas), podría "borrar" los caracteres que han sido emparejados y realizar más búsquedas en esa cadena. El carácter con el que se eliminará sería el separador, ya que se garantiza que no aparecerá en ninguno de los términos.

Aquí está:

ul { height:300px; font-size: smaller; overflow: auto; }

Input terms: <input type="text" id="findTerms"><br> <h3>Trincot''s Wipe Search</h3> Time: <span id="time"></span>ms<br> <ul id="result"></ul>

He excluido DOM I / O de la medición de tiempo.

Aquí hay un jsfiddle comparando los dos algoritmos uno al lado del otro. No debería ser difícil agregar un tercer algoritmo para comparar con otros algoritmos todavía.

Cuando el separador podría ser cualquier expresión regular.

... entonces la función anterior no se puede utilizar. Una forma de superar esto es introducir una cadena "sombra", siempre y cuando sea la cadena de opción, pero con solo 2 posibles caracteres diferentes (por ejemplo, .y x):

Uno de los dos indicaría que el carácter correspondiente (es decir, en la misma posición) en la cadena de opción se ha comparado con un término y, por lo tanto, ya no está disponible para la coincidencia de otro término.
El otro carácter indicaría que el carácter correspondiente en la cadena de opción aún está disponible para ser incluido en la coincidencia de un término.

Obviamente, esto hace que la función sea un poco más lenta, ya que puede haber coincidencias que deben ser rechazadas después de verificar con esta cadena de sombra:

ul { height:300px; font-size: smaller; overflow: auto; }

Input terms: <input type="text" id="findTerms"><br> <h3>Trincot''s Wipe Search</h3> Time: <span id="time"></span>ms<br> <ul id="result"></ul>

Este es un enfoque completamente diferente del que tomé en mi respuesta anterior, al cual no pude agregar todo lo que se indica a continuación (restricción de tamaño), así que ... es una respuesta por separado.

Árbol de sufijo generalizado: preprocesamiento de las opciones

Un árbol de sufijos generalizados es una estructura que en teoría permite buscar subcadenas en un conjunto de cadenas de una manera eficiente. Así que pensé en intentarlo.

La construcción de tal árbol de una manera eficiente está lejos de ser trivial, como puede verse en esta sorprendente explicación del algoritmo de Ukkonen , que se refiere a la construcción de un árbol de sufijos para una frase (opción).

Me he inspirado en la implementación que se encuentra aquí , que necesitaba una adaptación a:

Aplicar un mejor estilo de codificación (por ejemplo, deshacerse de variables globales no declaradas explícitamente)
Haz que funcione sin necesidad de agregar delimitadores después de los textos. Esto fue realmente complicado, y espero no perderme algunas condiciones fronterizas
Hacer que funcione para múltiples cadenas (es decir, generalizadas)

Asi que aqui esta:

"use strict"; // Implementation of a Generalized Suffix Tree using Ukkonen''s algorithm // See also: https://.com/q/9452701/5459839 class Node { constructor() { this.edges = {}; this.suffixLink = null; } addEdge(ch, textId, start, end, node) { this.edges[ch] = { textId, start, end, node }; } } class Nikkonen extends Node { constructor() { super(); // root node of the tree this.texts = []; } findNode(s) { if (!s.length) return; let node = this, len, suffixSize = 0, edge; for (let i = 0; i < s.length; i += len) { edge = node.edges[s.charAt(i)]; if (!edge) return; len = Math.min(edge.end - edge.start, s.length - i); if (this.texts[edge.textId].substr(edge.start, len) !== s.substr(i, len)) return; node = edge.node; } return { edge, len }; } findAll(term, termId = 1) { const { edge, len } = this.findNode(term) || {}; if (!edge) return {}; // not found // Find all leaves const matches = new Map; (function recurse({ node, textId, start, end }, suffixLen) { suffixLen += end - start; const edges = Object.values(node.edges); if (!edges.length) { // leaf node: calculate the match if (!(matches.has(textId))) matches.set(textId, []); matches.get(textId).push({ offset: end - suffixLen, termId }); return; } edges.forEach( edge => recurse(edge, suffixLen) ); })(edge, term.length - len); return matches; } addText(text) { // Implements Nikkonen''s algorithm for building the tree // Inspired by https://felix-halim.net/misc/suffix-tree/ const root = this, active = { node: root, textId: this.texts.length, start: 0, end: 0, }, texts = this.texts; // Private functions function getChar(textId, i) { return texts[textId].charAt(i) || ''$'' + textId; } function addEdge(fromNode, textId, start, end, node) { fromNode.addEdge(getChar(textId, start), textId, start, end, node); } function testAndSplit() { const ch = getChar(active.textId, active.end); if (active.start < active.end) { const edge = active.node.edges[getChar(active.textId, active.start)], splitPoint = edge.start + active.end - active.start; if (ch === getChar(edge.textId, splitPoint)) return; const newNode = new Node(); addEdge(active.node, edge.textId, edge.start, splitPoint, newNode); addEdge(newNode, edge.textId, splitPoint, edge.end, edge.node); return newNode; } if (!(ch in active.node.edges)) return active.node; } function canonize() { while (active.start < active.end) { const edge = active.node.edges[getChar(active.textId, active.start)]; if (edge.end - edge.start > active.end - active.start) break; active.start += edge.end - edge.start; active.node = edge.node; } } function update() { let prevNewNode = root, newNode; while (newNode = testAndSplit()) { addEdge(newNode, active.textId, active.end, text.length+1, new Node()); // Rule 2: add suffix-link from previously inserted node if (prevNewNode !== root) { prevNewNode.suffixLink = newNode; } prevNewNode = newNode; // Rule 3: follow suffixLink after split active.node = active.node.suffixLink || root; canonize(); // because active.node changed } if (prevNewNode !== root) { prevNewNode.suffixLink = active.node; } } texts.push(text); if (!root.suffixLink) root.suffixLink = new Node(); for (let i = 0; i < text.length; i++) { addEdge(root.suffixLink, active.textId, i, i+1, root); } // Main Ukkonen loop: add each character from left to right to the tree while (active.end <= text.length) { update(); active.end++; canonize(); // because active.end changed } } } function trincotSuffixTree(query, options, suffixTree, separator) { // Split query in terms at delimiter const terms = query.split(separator).filter(Boolean); if (!terms.length) return options; // Sort terms by descending size terms.sort( (a,b) => b.length - a.length ); // create Map keyed by term with count info const termMap = new Map(terms.map( (term, termId) => [term, { termId, count: 0, leftOver: 0, size: term.length }] )); terms.forEach( (term) => termMap.get(term).count++ ); function getNonOverlaps(offsets, leftOver, lastIndex = 0, offsetIndex = 0) { // All terms found? if (!leftOver) return []; let giveUpAt = Infinity; // While still enough matches left over: while (offsetIndex + leftOver <= offsets.length) { const { termId, offset } = offsets[offsetIndex++]; if (offset < lastIndex) continue; // overlap, try next if (offset >= giveUpAt) break; // Looking further makes no sense const termInfo = termMap.get(terms[termId]); //console.log(''termId'', termId, ''offset'', offset, ''size'', termInfo.size, ''lastIndex'', lastIndex); if (!termInfo.leftOver) continue; // too many of the same term, try next termInfo.leftOver--; const result = getNonOverlaps(offsets, leftOver - 1, offset + termInfo.size, offsetIndex); // If success, then completely backtrack out of recursion. if (result) return result.concat([offset + termInfo.size, offset]); termInfo.leftOver++; // restore after failed recursive search and try next // If a term-match at a given offset could not lead to a solution (in recursion), // and if we keep those matched character postions all unmatched and only start matching after // the end of that location, it will certainly not lead to a solution either. giveUpAt = Math.min(giveUpAt, offset + termInfo.size); } } let allTermsAllOptionsOffsets; // Loop through the unique terms: for (let [term, termInfo] of termMap) { // Get the offsets of the matches of this term in all options (in the preprocessed tree) const thisTermAllOptionsOffsets = suffixTree.findAll(term, termInfo.termId); //console.log(''findAll:'', JSON.stringify(Array.from(thisTermAllOptionsOffsets))); if (!thisTermAllOptionsOffsets.size) return []; // No option has this term, so bail out if (!allTermsAllOptionsOffsets) { allTermsAllOptionsOffsets = thisTermAllOptionsOffsets; } else { // Merge with all previously found offsets for other terms (intersection) for (let [optionId, offsets] of allTermsAllOptionsOffsets) { let newOffsets = thisTermAllOptionsOffsets.get(optionId); if (!newOffsets || newOffsets.length < termInfo.count) { // this option does not have enough occurrences of this term allTermsAllOptionsOffsets.delete(optionId); } else { allTermsAllOptionsOffsets.set(optionId, offsets.concat(newOffsets)); } } if (!allTermsAllOptionsOffsets.size) return []; // No option has all terms, so bail out } } // Per option, see if (and where) the offsets can serve non-overlapping matches for each term const matches = Array.from(allTermsAllOptionsOffsets, ([optionId, offsets]) => { // Indicate how many of each term must (still) be matched: termMap.forEach( obj => obj.leftOver = obj.count ); return [optionId, getNonOverlaps(offsets.sort( (a, b) => a.offset - b.offset ), terms.length)]; }) // Remove options that could not provide non-overlapping offsets .filter( ([_, offsets]) => offsets ) // Sort the remaining options in their original order .sort( (a,b) => a[0] - b[1] ) // Replace optionId, by the corresponding text and apply mark-up at the offsets .map( ([optionId, offsets]) => { let option = options[optionId]; offsets.map((index, i) => { option = option.substr(0, index) + (i%2 ? "<u>" : "</u>") + option.substr(index); }); return option; }); //console.log(JSON.stringify(matches)); return matches; } function trincotPreprocess(options) { const nikkonen = new Nikkonen(); // Add all the options (lowercased) to the suffic tree options.map(option => option.toLowerCase()).forEach(nikkonen.addText.bind(nikkonen)); return nikkonen; } const options = [''abbbba'', ''United States'', ''United Kingdom'', ''Afghanistan'', ''Aland Islands'', ''Albania'', ''Algeria'', ''American Samoa'', ''Andorra'', ''Angola'', ''Anguilla'', ''Antarctica'', ''Antigua and Barbuda'', ''Argentina'', ''Armenia'', ''Aruba'', ''Australia'', ''Austria'', ''Azerbaijan'', ''Bahamas'', ''Bahrain'', ''Bangladesh'', ''Barbados'', ''Belarus'', ''Belgium'', ''Belize'', ''Benin'', ''Bermuda'', ''Bhutan'', ''Bolivia, Plurinational State of'', ''Bonaire, Sint Eustatius and Saba'', ''Bosnia and Herzegovina'', ''Botswana'', ''Bouvet Island'', ''Brazil'', ''British Indian Ocean Territory'', ''Brunei Darussalam'', ''Bulgaria'', ''Burkina Faso'', ''Burundi'', ''Cambodia'', ''Cameroon'', ''Canada'', ''Cape Verde'', ''Cayman Islands'', ''Central African Republic'', ''Chad'', ''Chile'', ''China'', ''Christmas Island'', ''Cocos (Keeling) Islands'', ''Colombia'', ''Comoros'', ''Congo'', ''Congo, The Democratic Republic of The'', ''Cook Islands'', ''Costa Rica'', ''Cote D/'ivoire'', ''Croatia'', ''Cuba'', ''Curacao'', ''Cyprus'', ''Czech Republic'', ''Denmark'', ''Djibouti'', ''Dominica'', ''Dominican Republic'', ''Ecuador'', ''Egypt'', ''El Salvador'', ''Equatorial Guinea'', ''Eritrea'', ''Estonia'', ''Ethiopia'', ''Falkland Islands (Malvinas)'', ''Faroe Islands'', ''Fiji'', ''Finland'', ''France'', ''French Guiana'', ''French Polynesia'', ''French Southern Territories'', ''Gabon'', ''Gambia'', ''Georgia'', ''Germany'', ''Ghana'', ''Gibraltar'', ''Greece'', ''Greenland'', ''Grenada'', ''Guadeloupe'', ''Guam'', ''Guatemala'', ''Guernsey'', ''Guinea'', ''Guinea-bissau'', ''Guyana'', ''Haiti'', ''Heard Island and Mcdonald Islands'', ''Holy See (Vatican City State)'', ''Honduras'', ''Hong Kong'', ''Hungary'', ''Iceland'', ''India'', ''Indonesia'', ''Iran, Islamic Republic of'', ''Iraq'', ''Ireland'', ''Isle of Man'', ''Israel'', ''Italy'', ''Jamaica'', ''Japan'', ''Jersey'', ''Jordan'', ''Kazakhstan'', ''Kenya'', ''Kiribati'', ''Korea, Democratic People/'s Republic of'', ''Korea, Republic of'', ''Kuwait'', ''Kyrgyzstan'', ''Lao People/'s Democratic Republic'', ''Latvia'', ''Lebanon'', ''Lesotho'', ''Liberia'', ''Libya'', ''Liechtenstein'', ''Lithuania'', ''Luxembourg'', ''Macao'', ''Macedonia, The Former Yugoslav Republic of'', ''Madagascar'', ''Malawi'', ''Malaysia'', ''Maldives'', ''Mali'', ''Malta'', ''Marshall Islands'', ''Martinique'', ''Mauritania'', ''Mauritius'', ''Mayotte'', ''Mexico'', ''Micronesia, Federated States of'', ''Moldova, Republic of'', ''Monaco'', ''Mongolia'', ''Montenegro'', ''Montserrat'', ''Morocco'', ''Mozambique'', ''Myanmar'', ''Namibia'', ''Nauru'', ''Nepal'', ''Netherlands'', ''New Caledonia'', ''New Zealand'', ''Nicaragua'', ''Niger'', ''Nigeria'', ''Niue'', ''Norfolk Island'', ''Northern Mariana Islands'', ''Norway'', ''Oman'', ''Pakistan'', ''Palau'', ''Palestinian Territory, Occupied'', ''Panama'', ''Papua New Guinea'', ''Paraguay'', ''Peru'', ''Philippines'', ''Pitcairn'', ''Poland'', ''Portugal'', ''Puerto Rico'', ''Qatar'', ''Reunion'', ''Romania'', ''Russian Federation'', ''Rwanda'', ''Saint Barthelemy'', ''Saint Helena, Ascension and Tristan da Cunha'', ''Saint Kitts and Nevis'', ''Saint Lucia'', ''Saint Martin (French part)'', ''Saint Pierre and Miquelon'', ''Saint Vincent and The Grenadines'', ''Samoa'', ''San Marino'', ''Sao Tome and Principe'', ''Saudi Arabia'', ''Senegal'', ''Serbia'', ''Seychelles'', ''Sierra Leone'', ''Singapore'', ''Sint Maarten (Dutch part)'', ''Slovakia'', ''Slovenia'', ''Solomon Islands'', ''Somalia'', ''South Africa'', ''South Georgia and The South Sandwich Islands'', ''South Sudan'', ''Spain'', ''Sri Lanka'', ''Sudan'', ''Suriname'', ''Svalbard and Jan Mayen'', ''Swaziland'', ''Sweden'', ''Switzerland'', ''Syrian Arab Republic'', ''Taiwan, Province of China'', ''Tajikistan'', ''Tanzania, United Republic of'', ''Thailand'', ''Timor-leste'', ''Togo'', ''Tokelau'', ''Tonga'', ''Trinidad and Tobago'', ''Tunisia'', ''Turkey'', ''Turkmenistan'', ''Turks and Caicos Islands'', ''Tuvalu'', ''Uganda'', ''Ukraine'', ''United Arab Emirates'', ''United Kingdom'', ''United States'', ''United States Minor Outlying Islands'', ''Uruguay'', ''Uzbekistan'', ''Vanuatu'', ''Venezuela, Bolivarian Republic of'', ''Viet Nam'', ''Virgin Islands, British'', ''Virgin Islands, U.S.'', ''Wallis and Futuna'', ''Western Sahara'', ''Yemen'', ''Zambia'', ''Zimbabwe'']; /* * I/O and performance measurements */ let preprocessed; function processInput() { if (!preprocessed) { // Only first time const t0 = performance.now(); preprocessed = trincotPreprocess(options); const spentTime = performance.now() - t0; // Output the time spent on preprocessing pretime.textContent = spentTime.toFixed(2); } var query = this.value.toLowerCase(); const t0 = performance.now(); const matches = trincotSuffixTree(query, options, preprocessed, '' ''); const spentTime = performance.now() - t0; // Output the time spent time.textContent = spentTime.toFixed(2); // Output the matches result.innerHTML = ''''; for (var match of matches) { // Append it to the result list var li = document.createElement(''li''); li.innerHTML = match; result.appendChild(li); } } findTerms.addEventListener(''keyup'', processInput); processInput.call(findTerms);

ul { height:300px; font-size: smaller; overflow: auto; }

Input terms: <input type="text" id="findTerms"><br> <h3>Trincot''s Suffix Tree Search</h3> Preprocessing Time: <span id="pretime"></span>ms (only done once)<br> Time: <span id="time"></span>ms<br> <ul id="result"></ul>

Este método tiene bastante código detrás, por lo que supongo que podría no mostrar un rendimiento interesante para conjuntos de datos pequeños, mientras que para conjuntos de datos más grandes consumirá memoria: el árbol necesita mucha más memoria que la matriz de opciones original.