Método de procesado de una petición de búsqueda que incluye por lo menos un término de petición escrito incorrectamente en un sistema informático (30) que implementa un motor de búsqueda (38) que es accesible a los usuarios a través de una red de ordenadores,

comprendiendo el método las siguientes etapas implementadas por ordenador:

(a) recibir la petición de búsqueda de un usuario a través de la red de ordenadores, comprendiendo la petición de búsqueda una pluralidad de términos de búsqueda y estando dirigida a una base de datos de información (40) en la que se va a realizar la búsqueda;

(b) identificar, dentro de la petición de búsqueda, un término de búsqueda no coincidente que no produce una coincidencia dentro de la base de datos de información, y por lo menos un término de búsqueda coincidente que produce una coincidencia dentro de la base de datos de información;

(c) usar datos de correlación de términos de búsqueda para identificar una pluralidad de términos adicionales que se consideran relacionados con dicho por lo menos un término de búsqueda coincidente, basándose los datos de correlación de términos de búsqueda por lo menos en sumisiones de peticiones históricas; y

(d) comparar los términos adicionales identificados en la etapa (c) con el término no coincidente usando una función de comparación ortográfica para identificar un término adicional que es una sustitución candidata escrita correctamente para el término no coincidente, estando adaptada la función de comparación ortográfica:

para comparar una primera y segunda cadenas de caracteres ordenando la primera y segunda cadenas y comparando carácter a carácter la primera y segunda cadenas ordenadas;

y para generar una puntuación que indica un grado de similitud entre la primera y segunda cadenas de caracteres, y comparándose la puntuación con un valor umbral para determinar si un término adicional correspondiente es una sustitución candidata.

Sistema y método para corregir errores ortográficos en peticiones de búsqueda.

Apéndice y material bajo derechos de autor

La presente memoria incluye como apéndice un listado C++ de una función de comparación ortográfica usada para comparar dos cadenas de caracteres. El contenido del apéndice esta sujeto a protección de derechos de autor. El propietario de los derechos de autor no plantea ninguna objeción a la reproducción en facsímil del documento de patente o de partes del mismo, tal como aparece en los archivos o registros de la Oficina de Patentes y Marcas de los Estados Unidos u otra oficina de patentes, aunque en cualquier otro caso se reserva todos los derechos.

Campo

La presente invención se refiere a la búsqueda y recuperación de información, y más específicamente, se refiere a métodos para procesar peticiones de búsqueda.

Antecedentes

Muchos sitios de la Malla Multimedia Mundial y servicios en línea proporcionan programas de motor de búsqueda ("motores de búsqueda") para ayudar a los usuarios en la localización de artículos de interés de entre un dominio de artículos. Por ejemplo, sitios Webs tales como AltaVista e Infoseek proporcionan motores de búsqueda para ayudar a los usuarios a localizar otros sitios Web, y servicios en línea tales como Lexis y Westlaw implementan motores de búsqueda para ayudar a los usuarios a localizar artículos y dictámenes de tribunales. Adicionalmente, los comercios en línea proporcionan comúnmente motores de búsqueda para ayudar a los clientes a localizar artículos de entre un catálogo en línea.

Para realizar una búsqueda usando un motor de búsqueda, un usuario presenta una petición que contiene uno o más términos de búsqueda. La petición también puede identificar explícita o implícitamente un campo de registro a buscar, tal como el título, el autor o la clasificación por materia del artículo. Por ejemplo, un usuario de un sitio de librería en línea puede presentar una petición que contiene términos que el usuario cree que aparecen en el título de un libro. Un programa del servidor de peticiones del motor de búsqueda procesa la petición para identificar cualesquiera artículos que coinciden con la petición. Al conjunto de artículos identificados por el programa del servidor de peticiones se le hace referencia como "resultado de la petición" y se le presenta comúnmente al usuario en forma de una lista de los artículos localizados. En el ejemplo de la librería, el resultado de la búsqueda sería típicamente el conjunto de títulos de libros que incluyen todos los términos de búsqueda, y comúnmente se le presentaría al usuario en forma de un listado hipertextual de estos artículos.

Cuando el usuario de un motor de búsqueda escribe incorrectamente un término de búsqueda dentro de una petición, por ejemplo porque lo ha tecleado mal o no ha conseguido recordar el término, el término que se ha escrito incorrectamente no coincidirá normalmente con ninguno de los términos de la base de datos que cubre la búsqueda. En este caso, muchos motores de búsqueda simplemente devolverán un resultado de búsqueda nulo (vacío) . No obstante, la presentación de resultados de búsqueda nulos a los usuarios puede provocar una frustración significativa de estos últimos. Para reducir este problema, algunos motores de búsqueda ignorar eficazmente el (los) término (s) no coincidente (s) durante la búsqueda. Esta estrategia presenta la desventaja de no conseguir tener en cuenta información potencialmente importante especificada por el usuario y tiende a producir resultados de petición que contienen números relativamente grandes de artículos irrelevantes.

La patente US nº 5.694.592 da a conocer un proceso para medir el grado en el que documentos particulares son relevantes para una petición de búsqueda, tal como una petición de búsqueda de lenguaje natural. Este proceso conlleva el uso de un léxico semántico (esencialmente una correspondencia de palabras con categorías semánticas o significados asociados) para valorar los significados probables de palabras de peticiones específicas. El proceso valora también la importancia de cada palabra de búsqueda basándose en el número de documentos en los que aparece la palabra de petición. Si una palabra de petición dada no aparece en ninguno de los documentos en los que se está realizando la búsqueda, pero aparece en el léxico, el proceso puede sustituirla por un término relacionado seleccionado del léxico. En un ejemplo descrito en la patente US nº 5.694.592, el léxico se usa para sustituir la palabra de petición "partir", que no aparece en ningún documento, por la palabra "salir".

Un artículo titulado "Adapting a Full-text information Retrieval System to the Computer Troubleshooting Domain", publicado en ACM Press, "Online", Julio de 1994, de P.G Anick, describe la sintonización de un sistema de recuperación de información en el dominio de la resolución de problemas informáticos, en donde las peticiones de usuario tienden a ser breves y los términos en lenguaje natural se entremezclan con terminología de una variedad de sublenguajes técnicos. Anick menciona brevemente que se pueden usar datos de ficheros de registro de peticiones para detectar errores de ortografía pero no da a conocer cómo implementar la corrección ortográfica.

Sumario

La invención se define en las reivindicaciones.

La forma de realización de la invención afronta los problemas anteriores proporcionando un sistema y un método para corregir términos escritos incorrectamente dentro de peticiones de búsqueda. La forma de realización puede incluir una base de datos para datos de correlación que indican correlaciones entre términos de búsqueda. Los datos de correlación se pueden basar en las frecuencias con las cuales han aparecido históricamente juntos términos de búsqueda específicos dentro de la misma petición, y se pueden generar como, por ejemplo, a partir de un fichero de registro de peticiones. En el ejemplo, cada entrada dentro de la base de datos (implementada en forma de una tabla) comprende una palabra clave y una lista de "términos relacionados", en donde la lista de términos relacionados está compuesta por los términos que han aparecido en combinación con la palabra clave con el grado más alto de frecuencia.

El método de corrección ortográfica se puede invocar cuando se presenta una petición de búsqueda que incluye por lo menos un término coincidente y por lo menos un término no coincidente. Usando la base de datos de correlación, se puede generar inicialmente una lista de términos que se consideran en relación con el término o términos coincidentes. Esto se puede lograr, por ejemplo, extrayendo la lista de términos relacionados para cada término coincidente, y si la petición incluye múltiples términos coincidentes, combinando estas listas en una única lista de términos relacionados.

Los términos relacionados se pueden comparar en cuanto a ortografía con el (los) término (s) no coincidente (s) para identificar cualesquiera sustituciones adecuadas. Las comparaciones ortográficas se pueden realizar usando una función de comparación ortográfica de tipo anagramático, que genera una puntuación que indica el grado de similitud entre dos cadenas de caracteres. En un ejemplo, si se encuentra un término relacionado, con una ortografía suficientemente similar a un término no coincidente, el término no coincidente se puede sustituir automáticamente por el término relacionado. Alternativamente, al usuario se le puede solicitar que seleccione el (los) término (s) de sustitución de entre una lista de términos. Una vez que se han sustituido el término o términos no coincidentes, la petición modificada se puede usar para realizar la búsqueda. Al usuario también se le puede notificar sobre la (s) modificación (es) realizada (s) en la petición.

Una ventaja importante del método de corrección ortográfica antes descrito con respecto a métodos convencionales de corrección ortográfica es que resulta significativamente más probable que los términos de sustitución seleccionados sean los términos que fueron introducidos por el usuario. Esta ventaja se puede potenciar adicionalmente a través del uso de datos de correlación de términos de búsqueda, y particularmente datos de correlación que reflejan las sumisiones de peticiones históricas. El método incrementa la probabilidad de que los resultados de la petición contengan artículos que sean de interés para el usuario. Otra ventaja es que el método resulta muy adecuado para corregir... [Seguir leyendo]

1. Método de procesado de una petición de búsqueda que incluye por lo menos un término de petición escrito incorrectamente en un sistema informático (30) que implementa un motor de búsqueda (38) que es accesible a los usuarios a través de una red de ordenadores, comprendiendo el método las siguientes etapas implementadas por ordenador:

(a) recibir la petición de búsqueda de un usuario a través de la red de ordenadores, comprendiendo la petición de búsqueda una pluralidad de términos de búsqueda y estando dirigida a una base de datos de información (40) en la que se va a realizar la búsqueda;

(b) identificar, dentro de la petición de búsqueda, un término de búsqueda no coincidente que no produce una coincidencia dentro de la base de datos de información, y por lo menos un término de búsqueda coincidente que produce una coincidencia dentro de la base de datos de información;

(c) usar datos de correlación de términos de búsqueda para identificar una pluralidad de términos adicionales que se consideran relacionados con dicho por lo menos un término de búsqueda coincidente, basándose los datos de correlación de términos de búsqueda por lo menos en sumisiones de peticiones históricas; y

(d) comparar los términos adicionales identificados en la etapa (c) con el término no coincidente usando una función de comparación ortográfica para identificar un término adicional que es una sustitución candidata escrita correctamente para el término no coincidente, estando adaptada la función de comparación ortográfica:

para comparar una primera y segunda cadenas de caracteres ordenando la primera y segunda cadenas y comparando carácter a carácter la primera y segunda cadenas ordenadas; y para generar una puntuación que indica un grado de similitud entre la primera y segunda cadenas de caracteres, y comparándose la puntuación con un valor umbral para determinar si un término adicional correspondiente es una sustitución candidata.

2. Método según la reivindicación 1, en el que los datos de correlación de términos de búsqueda se basan por lo menos en frecuencias con las cuales han aparecido previamente términos de búsqueda en la misma petición.

3. Método según la reivindicación 1 ó la reivindicación 2, que comprende además la etapa de procesar sumisiones de peticiones históricas dentro de un fichero de registro para generar los datos de correlación de términos de búsqueda.

4. Método según la reivindicación 3, en el que la etapa de procesar sumisiones de peticiones históricas comprende aplicar una función de ventana al fichero de registro.

5. Método de la reivindicación 3 ó la reivindicación 4, en el que la etapa de procesar sumisiones de peticiones históricas comprende ignorar peticiones que produjeron resultados de petición nulos.

6. Método según cualquiera de las reivindicaciones anteriores, en el que el valor umbral depende de una longitud del término no coincidente.

7. Método según cualquiera de las reivindicaciones anteriores, que comprende además las siguientes etapas implementadas por ordenador:

(e) sin requerir una entrada de datos por el usuario, sustituir el término no coincidente por el término de sustitución candidato dentro de la petición de búsqueda para generar una petición de búsqueda modificada;

(f) aplicar la petición de búsqueda modificada a la base de datos de información con el fin de realizar una búsqueda; y

(g) notificar al usuario el resultado de la petición de la etapa (f) y la sustitución realizada en la etapa (e) .

8. Método según cualquiera de las reivindicaciones 1 a 6, en el que la etapa (d) comprende identificar una pluralidad de términos de sustitución candidatos escritos correctamente para el término no coincidente, y el método comprende además presentar al usuario una lista de los términos de sustitución candidatos para su selección.

9. Método según la reivindicación 8, en el que la etapa de presentar al usuario una lista comprende presentar cada término de sustitución candidato dentro de un respectivo hiperenlace que puede ser seleccionado por el usuario para

iniciar una búsqueda modificada.

10. Método según cualquiera de las reivindicaciones anteriores, en el que la etapa (b) comprende identificar una pluralidad de términos de búsqueda no coincidentes dentro de la petición de búsqueda, y el método comprende repetir la etapa (e) para cada uno de los términos de búsqueda no coincidentes con el fin de identificar un término de sustitución candidato para cada término de búsqueda no coincidente.

11. Método según cualquiera de las reivindicaciones anteriores, en el que la etapa (c) comprende:

(c1) para cada uno de entre una pluralidad de términos de búsqueda coincidentes, identificar una lista respectiva de términos relacionados; y (c2) combinar las listas de términos relacionados identificadas en la etapa (c1) .

12. Método según cualquiera de las reivindicaciones anteriores, que comprende además procesar peticiones de búsqueda sometidas al motor de búsqueda por una pluralidad de usuarios durante un periodo de tiempo para generar los datos de correlación (50) , indicando los datos de correlación correlaciones entre términos de búsqueda sobre la base de por lo menos frecuencias de apariciones anteriores de los términos de búsqueda dentro de la misma petición de búsqueda.

13. Método según la reivindicación 12, en el que dicho procesado de peticiones de búsqueda comprende actualizar los datos de correlación sustancialmente en tiempo real a medida que se reciben peticiones de búsqueda de los usuarios.

14. Método según la reivindicación 12 ó la reivindicación 13, en el que dicho procesado de peticiones de búsqueda comprende analizar sintácticamente un fichero de registro que incluye peticiones sometidas al motor de búsqueda.

15. Método según la reivindicación 14, en el que dicho procesado de peticiones de búsqueda comprende además aplicar una función de sesgado basada en el tiempo al fichero de registro para favorecer las sumisiones de peticiones de búsqueda recientes con respecto a las sumisiones de peticiones de búsqueda antiguas.

16. Método según la reivindicación 15, en el que dicha aplicación de una función de sesgado basada en el tiempo comprende aplicar una función de ventana al fichero de registro.

17. Método según cualquiera de las reivindicaciones 12 a 16, en el que dicho procesado de peticiones de búsqueda comprende ignorar peticiones de búsqueda que producen un resultado de petición nulo.

18. Método según cualquiera de las reivindicaciones 12 a 17, en el que dicho procesado de peticiones de búsqueda comprende además evaluar acciones de usuarios posteriores a la sumisión de peticiones para identificar peticiones de búsqueda que se considera que han producido un resultado satisfactorio, y ponderar con mayor intensidad las peticiones de búsqueda que produjeron un resultado satisfactorio en la generación de los datos de correlación.

19. Método según cualquiera de las reivindicaciones anteriores, en el que el sistema informático forma parte de un sitio Web, y la base de datos de información incluye información sobre productos que están disponibles para su compra a través del sitio Web.

20. Motor de búsqueda para permitir que los usuarios de una red de ordenadores realicen búsquedas de una base de datos (40) de artículos, comprendiendo el motor de búsqueda:

un sistema informático (30) que tiene almacenados en una memoria del mismo datos de correlación de términos de búsqueda, indicando los datos de correlación de términos de búsqueda (50) correlaciones entre términos de búsqueda sobre la base por lo menos de sumisiones de peticiones anteriores de usuarios; y un servidor de peticiones (38) que se ejecuta en el sistema informático, estando adaptado el servidor de peticiones para buscar en la base de datos de artículos usando peticiones de búsqueda recibidas de los usuarios, estando configurado el servidor de peticiones para procesar una petición de búsqueda de múltiples términos que incluye términos tanto coincidentes como no coincidentes mediante por lo menos:

el acceso a los datos de correlación de términos de búsqueda para identificar una pluralidad de términos adicionales que se consideran relacionados con el (los) término (s) coincidente (s) de la petición de búsqueda;

la comparación de la ortografía de los términos adicionales con la escritura de por lo menos un término no coincidente de la petición de búsqueda usando una función de comparación ortográfica para determinar si algunos de los términos adicionales es una sustitución candidata para el término no coincidente, estando adaptada la función de comparación ortográfica:

para comparar una primera y segunda cadenas de caracteres ordenando la primera y segunda cadenas y comparando carácter a carácter la primera y segunda cadenas ordenadas; y para generar una puntuación que indica un grado de similitud entre la primera y segunda cadenas de caracteres; y comparándose la puntuación con un valor umbral para determinar si un término adicional correspondiente es una sustitución candidata.

21. Motor de búsqueda según la reivindicación 20, en el que los datos de correlación de términos de búsqueda se basan por lo menos en frecuencias con las cuales han aparecido previamente términos de búsqueda dentro de la misma petición.

22. Motor de búsqueda según la reivindicación 20 ó la reivindicación 21, en el que el servidor de peticiones está configurado para, sin requerir una entrada de datos por el usuario:

sustituir un término no coincidente por un término adicional para generar una petición modificada; y buscar en la base de datos de artículos con la petición modificada.

23. Programa de ordenador que comprende elementos de programa de ordenador legibles por ordenador o por máquina para configurar un sistema informático con el fin de implementar el método según cualquiera de las reivindicaciones 1 a 19.

24. Medio portador de programa de ordenador que comprende un programa de ordenador según la reivindicación

23.