En escenarios como foros y salas de chat, para garantizar la experiencia del usuario, a menudo necesitamos bloquear muchas malas palabras. Para la búsqueda de palabras clave única, es naturalmente más eficiente en índice y métodos regulares. Sin embargo, si hay muchas palabras clave, si llama repetidamente índice o palabras regulares para que coincidan con el texto completo, el consumo de rendimiento es muy alto. Dado que la cadena de destino suele ser grande, es necesario asegurarse de que el resultado se obtenga en un recorrido. Según tales necesidades, es fácil pensar en formas de coincidir con cada personaje en todo el texto en secuencia. Por ejemplo, para este texto: "Mike Jordan había dicho" solo hazlo ", por lo que Mark ha sido un codificador". Si nuestra palabra clave es "Mike" y "Marca", entonces puede atravesar toda la oración. Cuando encuentre "M", vea si puede igualar "I" o "A". Si puede coincidir hasta el final, encontrará con éxito una palabra clave, de lo contrario continuará atravesando. Entonces la estructura de las palabras clave debe ser así:
Palabras clave var = {m: {i: {k: {e: {end: true}}}}, a: {r: {k: {end: true}}}}}De lo anterior, podemos ver que estos datos son una estructura de árbol, y todavía es lento crear una estructura de árbol basada en el grupo de palabras clave, mientras que las palabras clave ya se dan, por lo que puede crear dicha estructura de datos antes de coincidir. El código es el siguiente:
función buildtree (palabras clave) {var tblcur = {}, key, str_key, longitud, j, i; var tblroot = tblcur; for (j = keywords.length - 1; j> = 0; j - = 1) {str_key = Keywords [j]; Longitud = str_key.length; for (i = 0; i <longitud; i += 1) {key = str_key.charat (i); if (tblcur.hasownproperty (key)) {tblcur = tblcur [key]; } else {tblcur = tblcur [key] = {}; }} tblcur.end = true; // La última palabra clave tblcur = tblroot; } return tblroot;}Este código usa una declaración continua: tblcur = tblcur [key] = {}. La orden de ejecución aquí es la orden de ejecución de las declaraciones. Dado que el nivel de operación de [] es más alto que =, lo primero es crear un atributo clave en el objeto TBLCUR. Combinado con tblroot = tblcur = {}, el orden de ejecución es:
var tblroot = tblcur = {}; tblroot = tblcur; tblcur ['key'] = undefined; // ahora tblroot = {key: undefined} tblcur ['key'] = {}; tblcur = tblcur ['key'];A través del código anterior, se construyen los datos de consulta requeridos. Echemos un vistazo al método de escritura de la interfaz de consulta.
Para cada palabra de la cadena de destino, comenzamos desde la parte superior de estas palabras clave. Primero, palabras clave [a]. Si lo hay, mire la palabra clave [a] [b]. Si la última palabra clave [a] [b] ... [x] = true, significa que la coincidencia es exitosa. Si la palabra clave [a] [b] ... [x] = undefined, entonces la coincidencia se reiniciará desde la siguiente posición.
Function Search (content) {var tblcur, p_star = 0, n = content.length, p_end, coincida, // si debe encontrar un match_key, match_str, arrmatch = [], // almacenamiento del resultado arrlength = 0; // El índice de longitud de arrmatch while (p_star <n) {tblcur = tblroot; // Seguimiento de regreso a la raíz p_end = p_star; Match_str = ""; Match = false; do {match_key = content.charat (p_end); if (! (tblcur = tblcur [match_key])) {// El final de esta coincidencia p_star += 1; romper; } else {match_str += match_key; } p_end += 1; if (tblcur.end) // si coincidir con la cola {match = true; }} while (verdadero); if (match) {// Match Match arrmatch [arrlength] = {key: match_str, begin: p_star - 1, end: p_end}; arrlength += 1; p_star = p_end; }} return arrmatch;}Lo anterior es el núcleo de todo el sistema de coincidencia de palabras clave. Aquí usamos muy bien las características del idioma de JS, y la eficiencia es muy alta. Usé un "Soushen Ji" de 500,000 palabras para probarlo y encontré los 300 modismos dados. El efecto coincidente es de aproximadamente 1 segundo. Es importante destacar que el texto del objetivo se atraviesa a la vez, la longitud del texto del objetivo tiene poco efecto en el tiempo de consulta. El número de palabras clave que tienen un mayor impacto en el tiempo de consulta es el número de palabras clave. Cada palabra en el texto de destino atraviesa las palabras clave, por lo que tiene un cierto impacto en la consulta.
Análisis simple
Supongo que te preguntas cuándo lees el artículo anterior. Puede atravesar todas las palabras clave para cada palabra. Incluso si algunas palabras clave son parcialmente las mismas, es bastante lento atravesarlas por completo. Sin embargo, las propiedades de los objetos en JS se construyen utilizando una tabla hash. Los datos de esta estructura son muy diferentes de la transferencia de matriz simple, y la eficiencia es mucho más alta que la de la transferencia de matriz basada en el pedido. Es posible que algunos estudiantes no estén familiarizados con las estructuras de datos, por lo que hablaré brevemente sobre el contenido relevante de la tabla hash.
Primero, echemos un vistazo al almacenamiento de datos.
El almacenamiento de datos en la memoria consta de dos partes, una es el valor y el otro es la dirección. Piense en la memoria como un diccionario Xinhua, la explicación de la palabra es el valor, y el directorio es la dirección. El diccionario es ordenado por Pinyin, por ejemplo, "Ni" con la misma pronunciación está dispuesta en la misma pieza, es decir, la matriz está perfectamente dispuesta en un área de memoria. Esta estructura es una matriz, puede especificar "Ni" número 1 y 10 para acceder a ella. El diagrama de la estructura es el siguiente:
La ventaja de las matrices es que son fáciles de atravesar y pueden acceder directamente a los datos correspondientes a través de subíndices. Pero es muy difícil agregar o eliminar un cierto elemento. Por ejemplo, si desea eliminar el elemento 6, los datos después del elemento 5 deben avanzar en una posición. Si desea eliminar el primer bit, toda la matriz debe moverse, lo que consume mucho.
Para resolver el problema de la adición y eliminación de la matriz, aparecen listas vinculadas. Si dividimos el valor en dos partes, la parte se usa para almacenar el valor original, y la otra parte se usa para almacenar una dirección, que apunta a otra misma estructura, y así sucesivamente, forman una lista vinculada. La estructura es la siguiente:
Se puede ver claramente en la figura anterior que agregar y eliminar la lista vinculada es muy simple. Simplemente reescribe el elemento de destino y el siguiente elemento del elemento anterior y se completará. Sin embargo, es muy difícil consultar el valor de un artículo. Debe atravesarlo a su vez para acceder a la ubicación objetivo.
Para integrar las ventajas de estas dos estructuras, debe haber pensado en la siguiente estructura.
Esta estructura de datos es una estructura de tabla hash. La dirección de encabezado de la lista vinculada se almacena en la matriz, y se puede formar una tabla de datos bidimensional. En cuanto a cómo se distribuyen los datos, este es un algoritmo de hash, y una traducción regular debería ser un algoritmo de hash. Aunque hay muchos tipos de algoritmos, en principio, resuelven la clave a través de una función y luego colocan los datos de acuerdo con los resultados obtenidos de la solución. En otras palabras, se forma una asignación entre la clave y la dirección real, por lo que en este momento ya no accedemos a la matriz suscriptando la matriz o simplemente atravesándola, sino que localizamos los datos mediante la función inversa de la función hash. El objeto en JS es una estructura hash. Por ejemplo, definimos un OBJ. Obj.name a través del hash, y su posición en la memoria puede ser 90 en la figura anterior. Cuando queremos operar obj.name, la capa subyacente nos ayudará automáticamente a localizar la posición de 90 a través del algoritmo hash, lo que significa que comenzamos directamente a buscar la lista vinculada desde los 12 elementos de la matriz, en lugar de atravesar todo el bloque de memoria desde 0.
Definir un objeto obj {clave: valor} en js. La tecla se convierte en una cadena y luego se ha asaltado para obtener una dirección de memoria, y luego poner el valor en ella. Esto nos permite comprender por qué podemos agregar y eliminar atributos a voluntad, y por qué también podemos asignar atributos a las matrices en JS, y no hay una llamada matriz transfronteriza.
En situaciones en las que el volumen de datos es grande, la tabla hash tiene una ventaja muy obvia porque reduce muchos cálculos innecesarios a través del algoritmo hash. La llamada optimización del rendimiento es en realidad hacer que las computadoras sean menos computación; ¡La mayor optimización es no calcular!
Optimización de algoritmos
Ahora que comprende la implementación subyacente del algoritmo, puede considerar optimizar el algoritmo en retrospectiva. Sin embargo, antes de optimizar, debe enfatizar una cosa: ¡no busque el rendimiento! Por ejemplo, en este caso, podemos igualar hasta 5,000 palabras como máximo, por lo que el algoritmo existente es suficiente, y todas las optimizaciones son innecesarias. La razón por la que todavía hablo de optimización es mejorar mi comprensión del algoritmo y el programa, en lugar de realmente hacer la optimización de 1M.
Descubrimos que ninguna de nuestras palabras clave tiene una sola palabra, por lo que sería un desperdicio para nosotros atravesar las palabras clave de acuerdo con la unidad de una palabra. La optimización aquí es pre-estadística la longitud máxima y mínima de la palabra clave, y buscar en unidades de la longitud mínima cada vez. Por ejemplo, la palabra clave en mi caso de prueba es un idioma, y lo más corto es 4 caracteres, por lo que cada vez que coincino, coincino con 4 caracteres juntos. Si llego, continúe buscando en profundidad para encontrar la longitud máxima. En otras palabras, cuando construimos el árbol por primera vez, primero se construye con la longitud mínima, y luego se agrega textualmente.
Se realiza un cálculo simple. Según nuestro caso de prueba, para 300 modismos, solo necesitamos comparar una palabra una vez, y para una consulta de una sola palabra, debemos comparar 4 veces, y cada comparación tenemos que acceder a nuestra estructura de árboles, que es el consumo de rendimiento evitable. Más importante aún, la comparación aquí no es una comparación de cuerdas. ¡Nuestras palabras clave aquí existen como claves, y el efecto es el mismo que la clave en OBJ, que se ha hecho la clave y luego accede a la dirección correspondiente! Así que no se preocupe por la diferencia entre comparar una palabra y comparar cuatro palabras. ¡No comparamos cadenas!
Se trata de hacer coincidir múltiples palabras clave. No publicaré la versión optimizada del código porque generalmente no está disponible.