Un motor de búsqueda no es simplemente un algoritmo, sino que es mucho más complejo . Puede usar diferentes algoritmos para hacer que el motor de búsqueda sea más rápido de la forma en que lo hace google.
Hay cuatro actividades principales en un motor de búsqueda: rastreo, indexación, clasificación y publicación de consultas .
1. Gateando
- ¿Cuál es el mejor enfoque para adivinar los diacríticos árabes mediante programación?
- ¿Qué es lo más profundo que aprendiste al leer SICP?
- ¿Debo hacer investigación de pregrado en estructuras de datos teóricos y algoritmos, incluso si todavía no estoy seguro de si estoy persiguiendo la industria o la academia?
- Soy nuevo en Quora y no entiendo si las preguntas de coeficiente intelectual son una tendencia constante o si estoy atrapado en alguna forma de algoritmo infernal. Si es así, ¿cómo escapo?
- ¿Cuál es el mejor algoritmo de eliminación para un árbol de búsqueda binario sin usar un nodo padre adicional?
No tiene sentido molestarse en hacer el suyo, ya que hoy en día hay muchas buenas opciones de código abierto, como Nutch, Scrapy, Heritrix, etc., o podría hacerlo aún mejor y renunciar al rastreo al principio y usar CommonCrawlexcellent crawl, que se actualiza regularmente.
2. Indexación
No confíe en herramientas externas, es mejor escribir su propio indexador ya que aprenderá de qué se trata la búsqueda. Solo tenga en cuenta que la indexación no es ciencia espacial, un índice es simplemente una colección de listas de resultados para palabras clave y N-gramos (frases). Se trata de empacar esta colección de manera eficiente, y hacer que la búsqueda e inserción de nuevas entradas sea rápida y eficiente, teniendo en cuenta que se intercambian entre sí. Probablemente prestará más atención a la búsqueda rápida, aunque las aplicaciones más nuevas, como las sociales, son más intensas en escritura.
3. Ranking
Definitivamente querrá hacer su propia clasificación, comenzando con una implementación simple de Pagerank (Algoritmo de Pagerank: fue utilizado por Google inicialmente. Se han alejado de él y lo han mejorado. El documento original y la patente en la búsqueda de Google aún están disponibles si usted Búscalo en Google ) que quizás quieras modificar y experimentar, por ejemplo, con probabilidades de enlace de salida no uniformes de enlaces en páginas. No es tan difícil ejecutar Pagerank de manera eficiente incluso en grandes conjuntos de datos, necesitará implementar algunas particiones de bloque bastante básicas . Después de eso, comience a experimentar con diferentes heurísticas para elementos de página y enlace, como títulos, encabezados, textos de anclaje, frecuencias de términos, etc.
4. Servicio de consultas
Finalmente, para el servicio de consultas, haga cosas bastante básicas, por ejemplo, particiones de documentos simples en algunas máquinas con cierta previsión de cómo escalarlas más adelante.
Hoy en día es concebible llenar un índice simple (digamos unos KB por página) de más de mil millones de páginas en una sola máquina con múltiples unidades de TB y mucha RAM, 32 GB como mínimo. Si es más aventurero, agregue un SSD para la capa media y optimícelo para las lecturas de almacenamiento en caché, con escrituras poco frecuentes.
Es posible que un solo programador dedicado lo haga en 6-12 meses.
Ahora la parte del algoritmo
El algoritmo de los motores de búsqueda tiene dos partes. Uno está recopilando la parte de datos y el segundo está realizando una búsqueda en él .
En lo que respecta a la parte de recopilación de datos, la fuente de datos generalmente es el contenido de las páginas web. El contenido de las páginas web se desecha o rastrea. Los rastreadores modernos tienden a rastrear no solo el contenido de la página, sino también otra información importante que el propietario de un sitio web (editor) proporciona como parte de los metacampos. Nutch es un rastreador de código abierto que es más o menos bastante estable.
La parte de búsqueda es diferente de una búsqueda de consulta de base de datos normal. Es un campo especializado llamado búsqueda de texto libre. La búsqueda de texto libre significa que lo que usted consulta puede no ser parte de un formato de datos estándar como en el caso de las consultas de la base de datos, pero podría ser solo una oración normal en lenguaje natural. Por ejemplo, si vas a buscar la altura de Obama.
Consulta de base de datos
Seleccione altura desde peron donde nombre como ‘℅obama℅’
Consulta de motor de búsqueda
¿Cuál es la altura de Obama?
o
¿Qué altura tiene Obama?
Ambas consultas le darían resultados, pero el texto libre le quita el pastel cuando está ejecutando muchas de esas consultas y los datos a buscar son datos sin formato. La búsqueda de texto libre utiliza técnicas de procesamiento de lenguaje natural (tokenización, derivación, análisis, etc.) para obtener palabras clave de datos no estructurados y puntúa el rango de cada palabra clave en diferentes páginas web (llamadas documentos). La técnica de puntuación para averiguar el puntaje de una palabra clave es a través de TF-IDF (Frecuencia de documento invertida de frecuencia de término). Donde TF se calcula en base a la frecuencia de una palabra clave en un documento en particular, mientras que IDF se calcula como inverso de la frecuencia en diferentes documentos (inverso porque si una palabra clave es rara en todos los documentos, entonces debería ser importante).
La búsqueda de texto libre también utiliza un índice especial llamado índice invertido para almacenar identificadores de documentos contra palabras clave y viceversa. Esto ayuda a recuperar documentos y sus puntajes TF-IDF más rápido. Las herramientas de búsqueda de texto libre de código abierto incluyen Lucene, Solr, Elasticsearch.
Algoritmos utilizados por google
Google no muestra públicamente sus algoritmos, pero puede comenzar examinando el documento original escrito por los fundadores de Google.
- Aquí hay un sitio web que ofrece un poco más de información
- PageRank en Wikipedia
- Historial de cambios del algoritmo de Google
- ¿Cuál es el algoritmo de búsqueda utilizado por el motor de búsqueda de Google? ¿Cuál es su complejidad?
- La última hoja de trucos del algoritmo de Google
También podría ser extremadamente minucioso y examinar la investigación realizada por algunos de los empleados de Google antes de su tiempo en Google. Aunque probablemente sería mucho mejor solo investigar la colección de algoritmos de búsqueda y sus implementaciones. Es un campo muy amplio y tiene mucho material para trabajar. Google representa más de una década de trabajo intensamente enfocado por algunas de las personas más inteligentes del mundo, será un viaje interesante si intentas seguir a la sombra.
Representación visual de la historia de los cambios de algoritmo realizados por Google
