algorithm - ¿Cómo funciona la "increíble" barra de fósforos de Firefox?

string (4)

La pregunta es cómo se hace la coincidencia de cadenas para encontrar entradas que coincidan con la barra de direcciones de Firefox 3. La coincidencia de subcadenas en cada entrada puede ser lenta. ¿Qué algoritmo se puede usar para unir en cualquier ubicación de una manera rápida?

Creo que esto se deja en el almacenamiento subyacente: la base de datos SQLite donde Firefox almacena las páginas que visitas ofrece una función rápida para la comparación de subcadenas.

Creo que Firefox emite una consulta SQL a la base de datos. Esto es bastante rápido porque la base de datos está almacenada en la memoria caché.

El algoritmo de la barra de direcciones en Firefox 3.0 es un poco complicado. Obtendrá datos de dos (tres para Firefox 3.5 y posteriores) diferentes consultas:

Para la primera consulta, comprueba la tabla moz_inputhistory para ver si la cadena de búsqueda actual está almacenada en esa tabla. Estos resultados se ordenan por "rango", que es un número que determina qué tan recientemente se usa. Este número se degrada una vez al día. Esta búsqueda es lo que hace que la barra de direcciones sea adaptable a lo que seleccione con el tiempo (implementado en el error 95739 ).
En Firefox 3.5 y versiones posteriores, luego verifica la tabla moz_keyword de marcadores con una palabra clave que coincida exactamente con el texto de búsqueda.
La última consulta, revisa cada entrada en moz_places, que incluirá todas las visitas de historial y marcadores. Estos resultados están ordenados por la frecency .

Para los tres casos, se usa el siguiente algoritmo para comparar con las etiquetas, el título y la url (llamado "texto de búsqueda" a continuación). Esto es un poco difícil de explicar en palabras, por lo que podría ser más fácil ver el código fuente .

La cadena de búsqueda se divide en tokens determinados por espacios en blanco (cada palabra que no es de espacio en blanco es un token).
Para cada token, comience a comparar cada carácter del texto que se puede buscar y el token de una manera Unicode insensible a mayúsculas y minúsculas hasta que coincida por completo. Si un conjunto de caracteres no coincide, avance al siguiente " límite de palabras " en el texto que se puede buscar y vuelva a intentarlo.
Si hacemos coincidir cualquiera de los textos que se pueden buscar, aparecerá en la barra de direcciones.
Si no tenemos suficientes resultados (el valor predeterminado es 12), volveremos a realizar la búsqueda de la consulta que atraviesa cada marcador y visita de historial, y probaremos el texto que se puede buscar de una manera insensible a mayúsculas y minúsculas para cada token en cualquier lugar (no solo en los límites de las palabras).

¡Espero que eso lo explique de una manera comprensible!

La barra de awesome sugiere URLS por un algoritmo llamado frecency .

Según el sitio web de desarrolladores de Mozilla:

La palabra "frecency" en sí es una combinación de las palabras "frecuencia" y "actualidad".

La forma normal de hacer una coincidencia de subcadenas rápida es crear una estructura de datos que contenga todos los sufijos de todas las cadenas que desee buscar. Según la organización, esto se puede llamar "árbol de sufijos" o "matriz de sufijos". Por ejemplo, si tiene 1000 cadenas y cada una tiene 50 caracteres de longitud, tiene 1.000 x 50 sufijos no triviales, es decir, su matriz de sufijos tendrá 50.000 entradas.

Luego, para hacer el emparejamiento, realiza una búsqueda binaria (si es una matriz) o una búsqueda en árbol (si es un árbol) para buscar todos los sufijos en la estructura de datos cuyo comienzo coincide con la cadena escrita en el cuadro de búsqueda. Debido a que es el comienzo del sufijo que está buscando, puede usar procedimientos de búsqueda estándar (búsqueda binaria, descenso de árbol) para obtener el resultado rápidamente. Cada sufijo está vinculado a las cadenas en las que aparece.

Ejemplo: tiene dos cadenas "CAT" y "DOT". Su arreglo de sufijo se ve así (note lexiographic = orden alfabético):

#1 AT --> CAT #2 CAT --> CAT #3 DOT --> DOT #4 OT --> DOT #5 T --> DOT, CAT

Tenga en cuenta que hay seis sufijos pero dos de ellos son los mismos (la última "T" en "CAT" y "DOT") y ambos están representados por la misma entrada (# 5).

Ahora, cuando el usuario escribe en la búsqueda, por ejemplo, "OT" (que debe coincidir con "DOT"), puede realizar una búsqueda de pedidos lexiográfica simple en tiempo de registro, ya que ahora está buscando una coincidencia inicial en la matriz de sufijos.

Este es el principio básico de la búsqueda rápida de texto cuando el patrón de búsqueda no contiene comodines.