¿Qué estructura de datos o algoritmo se usa en los navegadores para buscar una palabra? ¿Los navegadores construirán un árbol trie o sufijo?Algoritmo utilizado por el navegador para buscar palabras en la página web
Gracias
Bala
La búsqueda con un árbol trie/sufijo es rápida, pero construir el trie para empezar es considerablemente más lento. Eso significa que solo tienen sentido cuando espera para llevar a cabo una gran cantidad de búsquedas sobre los mismos datos, por lo que puede amortizar el tiempo para construir el trie en muchas búsquedas.
El número promedio de búsquedas dentro de una página web es probablemente fraccionario (es decir, espera que el usuario cargue varias páginas antes de realizar una búsqueda, incluso una vez). Incluso cuando busca en una página, es probable que hacer muchas búsquedas en la misma página sea bastante raro.
Eso significa que una búsqueda lineal casi siempre será sustancialmente más eficiente en general que un árbol trie o sufijo. Supongo que si se toman la molestia de optimizarlo más allá de una simple llamada al strstr(), solo llegarán a algo en la familia Boyer-Moore de búsqueda de cadenas. Dado el número de búsquedas que espera en una página web, normalmente terminará en todas ellas antes de que pueda hacer la compilación inicial del trie, por lo que podría iniciar buscando con ella.
Para uso interactivo, su principal preocupación es producir resultados lo suficientemente rápido como para aparecer instantáneamente. Eso generalmente significa resultados dentro de los 100 ms aproximadamente. Con una buena implementación de Boyer-Moore-Horspool, es tiempo suficiente para buscar una cantidad de texto que sería demente para incluir en una sola página web (del orden de cientos de megabytes o gigabytes).
Si quiere ponerlo a prueba, le recomiendo la implementación de Ray Gardner de Boyer-Moore-Horspool (Bmhsrch.C, del sitio Bob Stout Snippets). Verdaderamente odio ver una página web lo suficientemente grande como para mantenerlo ocupado incluso 20 ms, sin mencionar 100 (aunque soy el primero en admitir que esta implementación en particular es excepcionalmente rápida).
Divertido, WebKit incluso contiene un comentario '// FIXME: ¿Podemos hacer Boyer-Moore o su equivalente en lugar de velocidad?' Http: // trac.webkit.org/browser/trunk/WebCore/editing/TextIterator.cpp?rev=34822#L1378 –
páginas web por lo general no son lo suficientemente grandes como para necesitar sofisticados algoritmos de búsqueda, por lo menos en la primera exploración. Quiero decir que probablemente puedas encontrar cualquier palabra con una búsqueda lineal simple en solo unos pocos ms. Una optimización podría ser construir un trie durante el primer análisis y luego usarlo para búsquedas posteriores.
En general, no creo que este sea uno de los grandes problemas en los algoritmos del navegador.
No estoy de acuerdo con usted en que se utilizará el escaneo lineal, porque la mayoría de los navegadores resaltarán todas las apariciones de la palabra a medida que escribe, y no creo que el escaneo lineal tenga sentido aquí. Podría ser que, en función del tamaño de la página web, se utilizará el escaneo lineal o trie. – Boolean
@Algorist: ¿cómo se resaltarían las palabras para hacer obsoleto el escaneo lineal? Para construir un trie, debe escanear linealmente al menos una vez, así que puede usarlo para encontrar los primeros resultados –
Pero hay una diferencia entre hacer un escaneo lineal una vez ... y hacerlo para cada palabra de búsqueda. – Boolean
Para comprender por qué un escaneo lineal es lo suficientemente rápido, considere cuánto más compleja es la representación de la página (que obviamente requiere al menos un escaneo lineal del HTML) y qué tan rápido se realiza. Creo que el navegador pasará mucho más tiempo resaltando las ocurrencias que buscándolos, de todos modos.
Además, la búsqueda se puede realizar de forma incremental. Diga, estoy buscando "algoritmo". Cuando escribo "a", el buscador puede encontrar (o comenzar a buscar de forma asincrónica) las ocurrencias de la letra "a" y los símbolos posteriores solo refinan los hallazgos actuales.
El uso simple de expresiones regulares es más que suficiente. Echa un vistazo a varias herramientas en línea.
¿Quiere decir cuando presiona Ctrl + F y escribe una palabra para buscar en esa página individual? –
@James Sí, la opción ctrl + F. – Boolean