ES2214535T3 - Procedimiento y sistema portatil de indexacion de documentos utilizando la descomposicion de palabras en n-grams. - Google Patents

Abstract

EL SISTEMA Y EL METODO SUMINISTRA UNA INDEXACION Y RECUPERACION DE DOCUMENTOS ALMACENADOS UTILIZANDO UNA DESCOMPOSICION DE PALABRAS EN LOS DOCUMENTOS EN SUBUNIDADES DE N-GRAMS O DE PALABRAS LINEALES. LOS DOCUMENTOS SE INDEXAN COMO PAGINAS EN UN NUMERO DE BANCOS. PARA CADA BANCO HAY UN INDICE DE BANCO. LOS NGRAMS INDIVIDUALES SE IDENTIFICAN PARA CADA PAGINA Y SE ALMACENAN EN EL INDICE DEL BANCO. CADA INDICE DE BANCO CONTIENE ADEMAS UN MAPA DE ENTRADAS QUE INDICA CUANDO UN N-GRAM DADO ESTA PRESENTE EN CUALQUIERA DE LAS PAGINAS DEL BANCO, Y ENTONCES SUMINISTRA UN INDICE A UN MAPA DE PAGINAS QUE INDICA ADEMAS QUE PAGINA EN EL BANCO CONTIENE EL N-GRAM. CUANDO SE INTRODUCE UNA INTERROGACION DE BUSQUEDA, LAS PALABRAS DE INTERROGACION SE DESCOMPONEN EN SU N-GRAMS. LOS N-GRAMS DE LAS PALABRAS DE INTERROGACION SE COMPARAN PRIMERO CON MAPAS DE ENTRADA PARA DETERMINAR SI LOS N-GRAMS DE LAS PALABRAS DE INTERROGACION APARECEN SOBRE CUALQUIER PAGINA EN EL BANCO. SI ES ASI, EL MAPA DE PAGINAS ASOCIADO SE RECORRE PARA DETERMINAR QUE PAGINA EN EL BANCO CONTIENE LOS N-GRAMS DE LAS PALABRAS DE INTERROGACION. LOS N-GRAMS EN LA PAGINA SE COMPARA CON LOS N-GRAMS DE LAS PALABRAS DE INTERROGACION PARA DETERMINAR LA PRESENCIA DE UNA CONCORDANCIA ENTRE AMBOS. LAS PAGINAS CONCORDANTES SON MARCADAS. CUANDO TODAS LAS PAGINAS EN TODOS LOS BANCOS HAN SIDO PROCESADAS, LAS PAGINAS SE CONSOLIDAN CON RESPECTO A LOS DOCUMENTOS A LOS CUALES PERTENECEN, DANDO COMO RESULTADO UNA LISTA DE DOCUMENTOS QUE CONCUERDAN CON LA INTERROGACION DE BUSQUEDA. LOS RESULTADOS SON MOSTRADOS AL USUARIO.

Description

Procedimiento y sistema portátil de indexación de documentos utilizando la descomposición de palabras en n-grams.

Antecedentes Campo de la invención

La presente invención se refiere al campo del procesamiento de documentos con escáneres ópticos y al reconocimiento óptico de caracteres, más particularmente, a sistemas y procedimientos para indexar palabras en un documento para su posterior búsqueda y recuperación.

Antecedentes de la invención

El reconocimiento óptico de caracteres (OCR) se utiliza ampliamente para capturar documentos impresos o escritos a mano en una forma legible para un ordenador, permitiendo que los documentos sean posteriormente buscados y recuperados utilizando sistemas de recuperación de información. Los sistemas normales de recuperación de información con capacidad para recuperar todo el texto indexan todas las palabras significativas de un documento de entrada en el sistema, proporcionando para cada palabra del índice una lista de identificadores de dónde está presente la palabra, normalmente contrastando documentos, páginas y algunos tipos de palabras equivalentes u otro tipo de conexión similar. Los documentos se recuperan como respuesta a una solicitud de búsqueda entrada mediante la equiparación exacta de las palabras de la solicitud de búsqueda con palabras del índice y recuperando los documentos indexados para las palabras. Normalmente se proporcionan operadores de búsqueda booleana para permitir solicitudes de búsqueda complejas.

Por consiguiente, la recuperación exacta de documentos de entrada depende ante todo de una entrada precisa y un análisis OCR. Los sistemas OCR son generalmente muy sensibles a los diferenciales de espaciamiento entre caracteres, tipo de fuente, tamaño de fuente, configuración de página, resolución de imagen, calidad de imagen. Así, incluso sistemas OCR de alta precisión, con índices de exactitud del 99%, interpretarán erróneamente uno de cada cien caracteres. dando como resultado sustituciones de letras, letras erróneas o errores ortográficos similares. Como resultado, un documento procesado con un OCR normal podrá contener en alguna parte de 3 a 8 ó más errores o palabras mal escritas por página. Sin incluir los errores tipográficos que podrían existir originalmente en el documento. Otro problema es que el sistema OCR interpretará juntas palabras separadas.

Las palabras mal escritas no se indexarán correctamente, y por lo tanto no se recuperarán como respuesta a las solicitudes de búsqueda que incluyan la palabra correctamente escrita. Del mismo modo, las palabras individuales de una cadena de palabras escritas juntas tampoco se indexarán completamente, sino que se indexarán únicamente como parte de toda la cadena de palabras, y por lo tanto un documento que contenga cualquiera de las palabras individuales de la cadena de palabras no se recuperará como respuesta a las solicitudes de búsqueda que especifiquen dichas palabras.

El documento XP000039810 MELTZER A C ET AL: "Text searching using an inversion database consisting of trigrams", CHINA, 23-27 JUNIO 1987, da a conocer un procedimiento de búsqueda de inversión de trigrams según el cual, para cada nuevo documento, sus palabras se convierten en trigrams y algunos de ellos se registran, es decir se realiza una entrada en una lista de registro. Cuando se entra una solicitud, el sistema convierte la solicitud en los trigrams que la forman, que se comparan con los de los documentos almacenados, y se obtiene una lista resultante de documentos de referencia que satisfacen la solicitud, y a continuación se envían los documentos al usuario. No se da a conocer el procesamiento posterior de los documentos recuperados o de los trigrams contrastados.

El documento XP0000576194 KIMBRELL R E: "Searching for text? Send an N-gram" BYTE, MAYO 1988 USA, vol. 13, nº 5, ISSN 0360-5280, páginas 297-312, da a conocer un procedimiento similar basado en N-grams para solicitudes de búsqueda en un documento, pero tampoco menciona el procesamiento posterior de los documentos recuperados.

Un procedimiento de búsqueda por n-grams similar se da a conocer en la patente FR-A-2 694 984.

Las soluciones normales a los problemas de mala escritura dependen de tesauros o de dispositivos similares para indexar errores de escritura comunes en las fuentes correctamente escritas. Un problema de este enfoque es que no tiene en cuenta los errores de escritura que no son comunes. Este enfoque también incrementa significativamente el tamaño del índice, y esto conduce a otro aspecto del diseño del sistema de recuperación de información.

Una segunda cuestión importante en los sistemas de recuperación de información es la eficacia y el tiempo requerido para crear y mantener un índice. Normalmente, un índice invertido se mantiene en forma de una única estructura de datos monolítica, como una lista de doble conexión o como una estructura de árbol. Cada vez que se añade un nuevo documento al sistema, que puede ser a diario en el caso de las bases de datos en línea, debe ajustarse todo el texto, y cada entrada de palabra del índice que aparece en los documentos de entrada debe actualizarse con los datos relevantes para los documentos de entrada. Esto convierte a la indexación en línea en inadecuada para muchos sistemas, de modo que la indexación se realiza fuera de línea, limitando la rapidez con la que se pueden buscar los documentos añadidos. Además, cuanto más detallado es el índice mayor es el tiempo consumido en el proceso de indexación. No obstante, un índice detallado puede proporcionar la ventaja de tiempos de búsqueda reducidos. Por lo tanto, existe un compromiso entre el tiempo de indexación y el tiempo de búsqueda.

Finalmente, otra cuestión relacionada con los sistemas de información es la capacidad para intercambiar documentos indexados para utilización con sistemas adjuntos o sistemas de clientes. Actualmente, muchas aplicaciones de software, y particularmente bases de datos y sistemas de información, tienen su base en arquitecturas de cliente-servidor. Además, el número de ordenadores portátiles aumenta continuamente. Estos factores hacen deseable el suministro de un sistema de indexación que permita que los documentos indexados se añadan al sistema o se eliminen del mismo para efectuar una búsqueda sin necesidad de efectuar un excesivo trabajo de reindexación. El sistema de recuperación de información convencional utiliza un índice monolítico invertido que no es portátil, porque el índice puede ocupar muchos megabytes, o incluso gigabytes, e indexar cientos o miles de páginas de documentos. Un índice de este tamaño o complejidad no puede transferirse adecuadamente a clientes remotos, dispositivos informáticos portátiles o medios de almacenamiento borrables.

Por consiguiente, es deseable proporcionar un sistema de indexación que compense los errores del documento de entrada, tanto si proceden del análisis OCR o de otra fuente, y permita la indexación rápida y la recuperación precisa de documentos que contengan errores de escritura u otros errores tipográficos. Además, es deseable proporcionar un sistema que permita una indexación rápida sin un incremento importante de los tiempos de búsqueda, y que además soporte la portabilidad de los documentos indexados.

Sumario de la invención

Un sistema y procedimiento de recuperación e indexación perfeccionado supera las limitaciones de los sistemas de recuperación de información existentes descomponiendo cada palabra en un número de "n-grams" o subunidades de palabra. Un n-gram es una combinación lineal ordenada de n caracteres tal como aparecen en una palabra determinada, particularmente letras o números, como "cho", "thi", "ment". Generalmente, un n-gram tiene un parámetro N_{p} que es el número de caracteres del n-gram. Un n-gram con un parámetro n-gram N_{p} de tres de denomina convenientemente un "trigram". Por ejemplo, la palabra "houseboat" está compuesto por los trigrams "hou", "ous", "use", "seb", "ebo", "boa", "oat". Obsérvese que ni "tbh" ni "hbt" son trigrams de "houseboat" aunque todas sus letras estén presentes en la palabra, ya que el orden de las letras y la relación entre las mismas tal como aparecen en la palabra son importantes.

En la presente invención, las palabras consecutivas de cada página de un documento se descomponen en sus n-grams, que se indexan y se almacenan. Indexando palabras por n-grams, antes que por palabras completas, pueden identificarse los errores de escritura, las palabras parciales o las palabras incluidas en cadenas de palabras buscando coincidencias entre n-grams de las palabras solicitadas y n-grams de los documentos, antes que coincidencias entre palabras completas. Por ejemplo, supongamos que la palabra "factory" se ha escrito incorrectamente como "factori" en un documento. Sus n-grams están almacenados en "fac", "act", "cto", "tor" y "ori". Estos n-grams se comparan con con los n-grams de la palabra de la solicitud de búsqueda "factory" escrita correctamente: "fac", "act", "cto", "tor" y "ory". Coincidirán cuatro de cinco n-grams y el documento se recuperará. de forma parecida, si la primera letra ha desaparecido por problemas del análisis OCR, las n-grams seguirán siendo "act", "cto", "tor" y "ory". En este caso, seguirán coincidiendo cuatro de cinco n-grams y el documento se recuperará. Evidentemente, los n-grams para palabras incluidas en una cadena de palabras impresas juntas serían similarmente identificables y separadamente contrastables.

Por consiguiente, para buscar y recuperar documentos, se entra una solicitud de búsqueda y las palabras de la solicitud de búsqueda se descomponen asimismo en sus n-grams. A continuación se comparan los n-grams de la palabra solicitada con los n-grams de palabras de las páginas de varios documentos. Cuando n-grams de una palabra solicitada coinciden con n-grams de una página, la página se recupera y los n-grams de la palabra solicitada se siguen comparando con cada n-gram de palabra. Esto permite determinar la precisión de la coincidencia entre las palabras solicitadas y las palabras de la página. El documento que contiene la página puede recuperarse y mostrarse al usuario. Una vez efectuada la determinación de la coincidencia entre las palabras solicitadas y las palabras del documento también puede realizarse una búsqueda booleana.

Los párrafos anteriores describen la idea básica de la descomposición en n-grams y del proceso de indexación. Pueden concebirse muchos sistemas diferentes de utilización de n-grams para analizar palabras o documentos. No obstante, es deseable utilizar la descomposición en n-grams en un sistema que suministre una indexación eficiente y una búsqueda rápida con una precisión elevada y que además proporcione portabilidad de los índices y de los documentos. Por consiguiente, otro aspecto separado de la invención es la utilización de un esquema de indexación jerárquico que almacene los datos que representan documentos en varios cajones, conteniendo cada cajón documentos con páginas de texto y datos de imágenes. Las páginas están listadas en varios bancos de un cajón. La descomposición en n-grams y la indexación se realizan en páginas específicas, antes que en documentos completos.

Cada cajón contiene varios bancos. Para cada banco existe un índice de banco. El índice de banco que almacena datos representa los n-grams que aparecen realmente en cada página del banco asociado. Al existir un número fijo conocido de n-grams de un tamaño determinado, cada índice de banco incluye además un mapa de entradas que indica para cada n-gram posible si existe algún ejemplo de los n-grams en cualquiera de las páginas listadas en el banco. Para cada n-gram del que existen ejemplos en cualquiera de las páginas del banco, el mapa de entradas proporciona a continuación acceso a otro mapa de páginas que identifica específicamente cada páginas del banco que incluye el n-gram. Este tipo de estructura de almacenamiento permite una utilización de la memoria muy compacta y eficiente durante la indexación y la recuperación.

Los bancos e índices de bancos proporcionan un sistema de recuperación rápido. Al entrar una solicitud, se determinan los n-grams de las palabras de la solicitud. Cada n-gram de las palabras de la solicitud se compara primero con el mapa de entrada para determinar si existen algunos ejemplos de los n-grams en cualquiera de las páginas del banco. Donde el mapa de entrada indica que alguna página contiene los n-grams, se recorren los mapas de páginas para determinar específicamente qué páginas requieren más procesamiento. Este procesamiento previo inicial identifica muy rápidamente únicamente las páginas que necesitan más búsqueda para una palabra de una solicitud determinada, eliminando de toda consideración las páginas que no contienen algún n-gram de las palabras solicitadas.

En una segunda etapa de procesamiento se accederá únicamente a las páginas del banco que contienen partes de la solicitud. Para cada una de dichas páginas, los n-grams de la página que están almacenados en el índice del banco se comparan a continuación con los n-grams de la palabra solicitada. Cuando un porcentaje suficiente de los mismos coinciden con los n-grams de una palabra solicitada, el documento asociado con la página se señala para recuperación.

Esta organización de documentos e índices proporciona la posibilidad de portar los documentos, ya que puede transferirse un cajón completo, incluyendo sus cajones, documentos, bancos e índices de bancos, desde el sistema de ordenador en el que estaba indexado el documento a otro sistema de ordenador, y buscarse en él sin necesidad de reindexar los documentos del cajón.

Breve descripción de los dibujos

La figura 1 es un diagrama de bloques de un sistema de indexación y recuperación de documentos utilizando la descomposición en n-grams.

La figura 2a es un modelo objeto de elementos de almacenamiento del sistema, que muestra las asociaciones de cajón, carpetas, documentos, bancos, listas de bancos, índice de bancos, lista libre y lista de documentos.

La figura 2b es una ilustración de la perspectiva del usuario de estos elementos de almacenamiento.

La figura 3 es una ilustración de la estructura de la lista de documentos.

La figura 4 es una ilustración de la estructura de un banco.

La figura 5 es una ilustración de la estructura de un índice de banco.

La figura 6 es una ilustración de un ejemplo de la relación entre un banco y un índice de banco.

La figura 7 es un diagrama de flujo del procedimiento global de indexación y búsqueda de documentos.

La figura 8 es un diagrama de flujo del proceso de indexación de un documento.

La figura 9 es un diagrama de flujo del proceso de indexación de una página de un documento.

La figura 10 es un diagrama de flujo del proceso de creación de palabras clave de una página para almacenamiento en el índice de banco.

La figura 11 es un diagrama de flujo del proceso de búsqueda.

La figura 12 es un diagrama de flujo de la operación de procesamiento previo en un banco.

La figura 13 es un diagrama de flujo del proceso de búsqueda de páginas seleccionadas de un banco a continuación del procesamiento previo.

La figura 14 es un diagrama de flujo del proceso de contraste de n-grams de las palabras solicitadas con n-grams de las palabras de una página.

Descripción detallada de la invención Arquitectura del sistema

Con referencia a la figura 1, se muestra un sistema para utilizar el sistema perfeccionado de indexación y recuperación de documentos según la presente invención, El sistema 100 incluye un ordenador 101 que presenta un almacenamiento secundario 107 para almacenamiento a largo plazo de documentos explorados, un dispositivo de entrada 109 y un dispositivo de salida 116 para recibir y emitir órdenes y datos, y una memoria direccionable 113 para almacenar los diversos módulos de códigos para su ejecución por el procesador 111.

Los dispositivos de entrada 109 incluyen un escáner 115 capaz de explorar documentos de entrada y producir archivos de mapas de bits tanto en escala de grises, bitonales, como en color para los documentos de entrada. El escáner 115 presenta preferiblemente por lo menos una resolución de 200 dpi. Los dispositivos de entrada 109 incluyen además un teclado 149 para entrar órdenes y datos. Los dispositivos de salida 116 incluyen una impresora 117 para imprimir documentos, incluyendo documentos explorados, u otros documentos residentes en el sistema 100. Los dispositivos de salida 116 también incluyen una pantalla 151 para visualizar un interfaz de usuario para el sistema ante el usuario, junto con resultados de búsqueda y otra información.

La memoria direccionable 113 incluye varios módulos de código que juntos comprenden una aplicación ejecutable que gestiona el sistema 100 según la presente invención. Más particularmente, la memoria direccionable 113 incluye una subrutina de ejecución de aplicaciones 119, una subrutina de ejecución de índices 121, una subrutina de ejecución de búsquedas 123, un módulo de referencia de documentos 125, un módulo de indexación de páginas 127, un módulo de ejecución de búsquedas 129, un módulo de listas de búsquedas 131 y un módulo de reconocimiento óptico de caracteres 133. El funcionamiento de estos diversos módulos se describe más adelante, después de una descripción de los elementos de almacenamiento que soportan la indexación de documentos portátiles. Se utiliza una memoria intermedia de índices/búsquedas 143 para almacenar temporalmente datos generados durante la indexación y las etapas de búsqueda. Se utiliza una memoria intermedia 145 para almacenar temporalmente datos de documentos durante la búsqueda. Un archivo de palabras vacías 135 mantiene una lista de palabras que están excluidas de la indexación. El archivo de palabras vacías 135 se suministra con el sistema 100, y puede ser modificado por el usuario.

Se accede al sistema 100 a través de la subrutina de ejecución de aplicaciones 119 que proporciona una interfaz de usuario adecuada en la pantalla 151, permitiendo al usuario entrar documentos al sistema 100 a través del escáner 115, u otras fuentes, tales como archivos de texto existentes, archivos de imágenes, archivos gráficos y similares, para entrar solicitudes de búsqueda que contengan combinaciones de palabras, caracteres universales y operadores booleanos o SQL, y para revisar los resultados de las solicitudes de búsqueda en los dispositivos de salida, como la pantalla 151 o la impresora 117.

La memoria direccionable 113 incluye además una base de datos 141 de estructuras de almacenamiento útiles para implementar la indexación por descomposición en n-grams según la presente invención. Con referencia a la figura 2a, se muestra un modelo objeto de estas estructuras de almacenamiento en la memoria direccionable 113. La figura 2b ilustra la perspectiva del usuario de estas estructuras de almacenamiento.

La memoria direccionable 113 incluye además uno o más cajones 201. Cada cajón 201 dispone preferiblemente de un nombre de cajón, un nombre lógico, y tipo de soporte, ya sea un soporte portátil o fijo. Este último atributo permite que los cajones 201 sean transferidos a varios dispositivos informáticos en soportes de almacenamiento portátiles.

Cada cajón 201 incluye además una lista jerárquica de cero o más carpetas 203. Cada carpeta 203 dispone de un nombre de carpeta e incluye cero o más documentos 205 u otras carpetas 203.

Cada documento 205 dispone preferiblemente de un nombre de documento para su reconocimiento por el usuario, y un número único de documento utilizado por el sistema 100. Un documento 205 comprende por lo menos un archivo de texto 207. Adicionalmente, un documento 205 puede incluir un archivo de imagen 209, un archivo de icono 213 y un archivo de estructura de archivo de documento (DFS) 211. El archivo de texto 207 contiene los datos de texto del documento en un formato ASCII o similar. Los datos de texto se producirán generalmente a partir del procesamiento OCR de datos de imagen. Los datos de texto también pueden ser creados directamente a partir de entradas de usuario. Los datos de texto también pueden entrarse, por ejemplo cuando el documento 205 es un archivo de gráficos vectoriales o mapas de bits, y el usuario desea incluir un comentario o descripción del archivo con fines de indexación. El archivo de texto 207 contiene sus datos en una o más páginas 215. Cada página se identifica mediante su número de página, nombre de documento, nombre de carpeta y nombre de cajón.

El archivo de imagen 209 es un mapa de bits de color o en escala de grises, bitonal, resultante del exploración y la digitalización de un documento de entrada correspondiente, o de otro proceso similar. Los datos del archivo de imagen 209 se almacenan similarmente en páginas 215.

El archivo DFS 211 correlaciona los datos del archivo de texto con los datos del archivo de imagen. El archivo DFS 211 contiene para cada línea de texto del archivo de texto 207 un mapa para una página de imagen 215, y un rectángulo de contorno definido por coordenadas de pixel (preferiblemente las esquinas superior izquierda e inferior derecha) del lugar en que aparece la línea de texto en la página de imagen 215. Este mapa permite al usuario acceder a los datos de texto de una página cuando ve la imagen de la página. El archivo DFS 211 también mantiene preferiblemente un recuento de páginas para el número de páginas de texto e imagen del documento 205. El archivo DFS 211 mantiene además datos de referencia sobre cada página 215 del documento 205, incluyendo número de página, número de documento y nombre, nombre completo de la ruta y nombre de archivo de icono.

El archivo de icono 213 contiene imágenes croquizadas en mapas de bits de cada página del documento 205. Las imágenes en escalerilla se visualizan para el usuario durante las operaciones de búsqueda y recuperación o mientras el usuario accede al documento 205. En la forma de realización preferida, cuando el documento contiene sólo datos de texto producidos sin exploración o similares, no existe archivo acompañante de imágenes 209 ni de icono 213.

Cada cajón 201 está asociado a una lista de documentos 225. La lista de documentos es un índice de todos los documentos 205 del cajón 201. La figura 3 ilustra la estructura de la lista de documentos 225. La lista de documentos 225 almacena un número variable de entradas 311, hasta un límite máximo D_{max}. En la forma de realización preferida, el D_{max} está limitado por el número global de páginas de todos los documentos del cajón 201, disponiendo cada cajón de capacidad para manejar hasta 1.044.480 páginas. Cada entrada 311 incluye el nombre completo de la ruta de cada documento 205 del cajón 201. Cada documento 205 tiene un único número de documento 301 en la lista de documentos 225 como resultado de su posición en la lista de documentos 225. Se mantiene preferiblemente un valor de estado 303 para indicar para cada entrada 311 si está disponible para almacenar un documento. La lista de documentos 225 mantiene un recuento del número 307 de entradas de documentos 311, y un recuento del número 309 de entradas sin utilizar, que se crean al eliminar documentos existentes.

El sistema 100 incluye además por lo menos un banco 217. La figura 4 es una ilustración de la estructura de un banco 217. Cada banco 217 contiene una lista de páginas de varios documentos del sistema 100, hasta un número predeterminado P_{max} de entradas 413. En la forma de realización preferida, un banco 217 contiene hasta 255 entradas, o referencias de página. En otras formas de realización el P_{max} puede ser superior, dando como resultado la indexación de más páginas, o el P_{max} puede ser inferior, con el resultado de un número inferior de páginas indexables, pero menos requisitos de almacenamiento. Las páginas del documento se listan con su número de documento 301 de la lista de documentos 225 para el cajón 201, y a continuación mediante un número de página 403 dentro del documento 205. Para cada entrada 413, se mantiene preferiblemente un valor de estado 405 que indica si se ha referenciado una página en la entrada. Cada entrada 413 dispone además de una información complementaria de banco 411 que es la posición de la entrada 413 dentro del banco 217; la información complementaria del banco 411 no está realmente almacenada en la entrada 413. Cada banco 217 mantiene preferiblemente un número 407 de entradas sin utilizar que se actualiza cuando se referencian nuevas páginas, y otras se encuentran sin referenciar en el banco 217. En la forma de realización preferida, un cajón 201 puede incluir 4096 bancos 217, dando como resultado hasta 1.044.480 páginas de datos indexados para cada cajón 201. Cada banco 217 dispone de un número de banco 409 que los identifica de forma exclusiva en el cajón 201 y en la lista de bancos 219; el número de banco 409 puede almacenarse en el propio banco 217 o puede identificarse mediante el nombre de archivo del banco 217. Un número de banco 409 y una información complementaria de banco 411 forman conjuntamente una referencia de banco para una página.

Cada banco 217 está asociado con un índice de banco 223 y una lista libre 221. Cada índice de banco 223 identifica los n-grams encontrados en cada entrada de página 413 de un banco 217. Con referencia a la figura 5, se muestra la estructura preferida del índice de banco 223. En la forma de realización preferida, el índice de banco 223 no incluye directamente una lista de todos los n-grams como datos. Antes bien, cada n-gram tiene asignado un número único que se utiliza para indexar un número fijo de correlaciones de entradas de n-grams 505.

En primer lugar se selecciona el conjunto de caracteres y el rango de caracteres indexables por el sistema 100 para indexación. El número total de caracteres indexables se denomina C_{max}. Por consiguiente, el número total L de de n-grams es:

L = [Cmax]^{N_{p}}.

En la forma de realización preferida, los caracteres indexables son "A"-"Z", "0"-"9". Todos los caracteres de puntuación y caracteres especiales, que normalmente no se utilizan para buscar datos, se correlacionan preferiblemente con un carácter, como por ejemplo "\sim". Esto permite indexar palabras como "AT&T" como "AT\simT" y números como "3.1415926" como "3\sim1415926". Además, cuando algunos de los últimos caracteres de una palabra son insuficientes en número para forma por si mismos un n-gram, puede utilizarse "\sim" para completar el n-gram. Por ejemplo, el trigram de "at" sería "at\sim". Los caracteres internacionales pueden correlacionarse con equivalentes correspondientes en inglés. Los caracteres en minúsculas se convierten en sus equivalentes en mayúsculas. En la forma de realización preferida el resultado son 37 caracteres para cada posición del n-gram. Por consiguiente, en la forma de realización preferida existen 50.563 (37^{3}) trigrams. Los 37 caracteres están ordenados de cualquier manera útil, como por su valor ASCII o por otros medios. A continuación se listan los n-grams posibles y se numeran con un número de n-gram. Por ejemplo, suponiendo primero números, a continuación letras y finalmente "\sim", el orden podría ser "000", "001", ..."00A", ..."00Z". "00\sim", ..."\sim\sim\sim". En una forma de realización preferida, el número de n-grams podría calcularse del modo siguiente:

Número de n-gram =	(1^{er} nº de letra de n-gram)*car_max^{N-1} +
	(2º nº de letra de n-gram)*car_max^{N-2} +
	(3^{er} nº de letra de n-gram)*car_max^{N-3} +
	...
	(N-1^{avo} nº de letra de n-gram)*car_max +
	(N^{avo} nº de letra de n-gram)

donde nº de letra de n-gram. es el número ordenado de letras tal como aparecen en el n-gram, N es el parámetro n-gram N_{p}, y car_max es igual a C_{max}. En la forma de realización preferida, C_{max} es 37, y el parámetro n-gram N_{p} es 3, de modo que la ecuación se reduce a:

Número de trigram =	(1^{er} nº de letra de trigram)*37^{2} +
	(2º nº de letra de trigram)*37 +
	(3^{er} nº de letra de trigram)

En una forma de realización alternativa, una tabla de consulta 227 almacena los n-grams, y la posición de un n-gram determinado en la tabla es su número n-gram.

Cada índice de banco 223 incluye un número fijo de mapas de entradas de n-gram 505 igual en número al número total L de n-grams que se utilizan. Cada correlación de entradas n-gram 505 mantiene un valor de índice para un mapa de páginas de índices 507, si un mapa de páginas de índices 507 ha sido asignado al n-gram asociado con la entrada de n-gram 505. Cada unidad de valor de índice representa el número total de elementos de un mapa de páginas de índices 507. Una posición de índice 501 almacena la dirección del primer mapa de páginas de índices 507. El (valor de índice -1) de un mapa de entradas de n-grams 505 se añade a la posición de índice 501 para alcanzar el mapa de páginas de índices 507 asociado con el mapa de entradas de n-grams 505. Debido a que muchos n-grams pueden no aparecer en algunas de las entradas de página 413 del banco 217, los mapas de entradas de n-grams 505 permiten al sistema 100 determinar rápidamente para qué n-grams existen ejemplos actuales en la página, y por lo tanto los mapas de páginas de índice reales 507 que deben analizarse más durante la búsqueda.

Para cada mapa de entradas de n-grams 505 donde el valor del índice es distinto de cero existe un mapa de páginas de índices 507. Cada mapa de páginas de índices 507 contiene datos que indican qué páginas 403 del banco 217 contienen el n-gram. El mapa de páginas de índices 507 contiene un bit para cada entrada de página 413 posible del banco 217. En la forma de realización preferida, el número de bits de cada mapa 507 corresponde al número máximo de entradas P_{max} del banco 217. La posición del bit en el mapa de páginas de índices 507 corresponde a la información complementaria del banco 411 de una entrada de página 413 de un banco 217. El bit se ajusta si la entrada de página 413 contiene el n-gram asociado con el mapa de páginas de índices 507, y no se ajusta en caso contrario. En la forma de realización preferida con 255 entradas de página 413 en un banco 217, cada mapa de páginas de índices 507 contiene 32 bytes (256 bits) para correlacionar los n-grams en las entradas de página 413. En otras formas de realización pueden utilizarse otras formas de correlacionado, como listas de punteros. La actualización de los mapas de página de índice 507 se describe más adelante con mayor detalle.

La figura 6 es un ejemplo de la relación de indexación entre un banco 217 y un índice de banco 223. La figura 6 muestra una parte de un banco 217 que contiene varias entradas de página 413a-f, con un número total de entradas P_{b}. Varias de las entradas están marcadas como "utilizada" en su valor de estado 405, y cada una de dichas entradas 413 incluye un número de documento 303 que indica a qué documento pertenece de la lista de documentos 225 (que no se muestra), y un número de página 403 que indica la página del documento. Obsérvese que las entradas 413 proceden de documentos muy diferentes, y que entradas procedentes del mismo documento, como las entradas 413b,c, son sólo páginas seleccionadas del documento. Se indica la información complementaria 411 para cada entrada 413.

El índice de banco 223 incluye una parte del listado completo de mapas de entradas de n-grams 505a-f. Cada uno de estos mapas de entradas de n-grams 505a-f incluye un valor de índice 601 que indica qué mapa de páginas de índices 507a-f, si existe, se asigna al n-gram asociado con el mapa de entradas de n-grams. Así, el primer (tal como aparece en la ilustración; podría se el n^{avo} del índice de banco 223) mapa de entradas de n-grams 505a tiene un valor de índice 601 igual a cero, indicando que el n-gram asociado con el mapa no aparece en ninguna página del del banco 217, y por lo tanto no se asigna ningún mapa de páginas de índices 507 al mapa de entradas de n-grams 505. Lo mismo ocurre con el tercer mapa de entradas de n-grams 505c.

El segundo mapa de entradas de n-grams 505b, no obstante, presenta un valor de índice igual a 2, indexando en el segundo mapa de páginas de índices 507b. Por lo tanto, existe por lo menos una página del banco 217 que presenta un ejemplo del n-gram asociado con el mapa de entradas de n-grams 505b, sea cual sea este n-gram. de forma similar, el cuarto mapa de entradas de n-grams 505d indexa en el mapa de páginas de índices 507d, el mapa de entradas de n-grams 505e indexa en el tercer mapa de páginas de índices 507c, y el mapa de entradas de n-grams 505f indexa en el primer mapa de páginas de índices 507a.

Cada mapa de páginas de índices 507 incluye un conjunto de bits que se correlacionan con las entradas 413 del banco 217, El valor de un m^{avo} bit en un mapa de páginas de índices 507 indica si el n-gram asociado con el mapa de entradas de n-grams 505 para este mapa de páginas de índices 507 aparece en la página representada por la entrada m^{ava} 413. El primer bit de cada mapa de entradas de índices 507 correlaciona con la primera entrada 413a, el segundo con la segunda entrada 413b, y así respectivamente.

Por ejemplo, en la caja 603 se muestran las correlaciones para la cuarta entrada 413d en el banco 217. En ambos mapas de página de índice primero y segundo, 505a,b, el bit correspondiente a la entrada 413d no es fijo. Esto indica que los n-grams asociados con los mapas de entradas de n-grams 505b y 505f no aparecen en la página 87 del número de documento 711. No obstante, los bits de los mapas de la página de índice 507c,d son fijos, por lo tanto los n-grams asociados con los mapas de entradas de n-grams 505d,e no aparecen en esta página. Similarmente, el bit (P_{max})^{avo} del mapa de páginas de índices 507b indica que el n-gram asociado con este mapa aparece en la página 93 del número de documento 818.

Con referencia de nuevo a la figura 5, el índice de banco 223 almacena además datos que representan los n-grams que aparecen en las páginas que se identifican mediante las entradas de página 413 del banco 217. Esta es el área del índice de banco 223 en la que se realiza la búsqueda real para localizar documentos que coincidan con una solicitud de búsqueda. Estos datos se almacenan en una tabla de longitud variable 517 de claves de página 509, una para cada entrada de página 413. Una clave de página 509 es un campo de longitud variable que presenta la forma siguiente:

[k_{i}, n-gram \ i_{1}, \ n-gram \ i_{2}, ... \ n-gram \ i_{k}]

[k_{(i+1)}, \ n-gram \ (i+1)_{1}, \ n-gram \ (i+1)_{2} ...n-gram \ (i+1)_{k}] ...

donde k_{i} es el número de n-grams de la palabra i^{ava} de la página, y n-grams i_{(1...k)} es la lista de números de n-gram de la i^{ava} palabra. Cada grupo de valores de [k] [n-gram 1, n-gram 2, ... n-gram k] se designa como una "clave de palabra". El conjunto de claves de palabra para todas las palabras de la página es la clave de página 509, Obsérvese que los propios n-grams no se almacenan en la forma de realización preferida, sino que se almacena un número de n-gram que identifica unívocamente cada n-gram en la clave de página 509. Utilizando números de n-gram en lugar de los propios n-gram se ahorra memoria. Cada n-gram requiere 1 byte para cada carácter, por lo tanto un trigram son 3 bytes. Pero cada número de n-gram sólo requiere:

log_{2}([Cmax]^{N,})

bits. Por lo tanto, un trigram requiere 15,6 bits, ó 2 bytes.

Suponiendo un tamaño de datos de texto máximo de 32k para una página, el tamaño máximo de una clave de página 509 en la forma de realización preferida será sólo de 128k. En la práctica, el tamaño medio de cada página es de aproximadamente 2k, y el de cada clave de página 509 es de aproximadamente 8k.

Para acceder a claves de página individuales 509 se proporciona una tabla de posición de página de tamaño fijo 515. Cada entrada incluye una posición de clave de página 511 y un tamaño de clave página 513 para cada clave de página 509. En la forma de realización preferida, existe una entrada para cada una de las entradas de página 413 del banco 217. La posición de clave de página 511 es una posición para el inicio de la clave de página de longitud variable 509 correspondiente a la entrada de la tabla. El tamaño de clave de página 513 es el número total de bytes de la clave de pagina correspondiente 509, incluyendo todas las entradas de n-grams y valores k. El mantenimiento del tamaño de clave de página 513 permite al sistema 100 suprimir páginas indexadas del sistema, y disponer permanentemente de información sobre el área disponible para añadir e indexar una página nueva, evitando reducir el espacio de almacenamiento.

Cada banco 217 lleva asociada una lista libre 221, que almacena información de qué entradas de página 413 del banco 217 están disponibles para indexar, incluyendo dónde se ha suprimido una entrada de página 413 previamente indexada. Cuando una entrada de página 413 se suprime de un banco 217, la posición de la clave de página 511, y el tamaño de la clave de página 513 del índice de banco 223 se almacenan en la lista libre 221 y a continuación la posición de la clave de página 511 se pone a cero en el índice de banco 223.

Una lista de bancos 219 contiene datos de todos los bancos 217 de un cajón 201. La lista de bancos 219 mantiene para cada banco 217 un recuento del número de entradas libres 413 del banco 217. Estos valores se actualizan cuando se añaden páginas nuevas a los bancos 217, o se borran las antiguas. En la forma de realización preferida, la lista de bancos 219 incluye un recuento de entrada libre para hasta 4.096 bancos 217, según su número de banco. La Tabla 1 ilustra la estructura de la lista de bancos 219:

Banco 1	Banco 2	Banco 3		Banco 4.096
Libre	Libre	Libre	-	Libre
Recuento	Recuento	Recuento		Recuento

Con referencia de nuevo al archivo DFS 211, en la forma de realización preferida contiene para cada página 215 de su documento asociado 205 el número de banco del banco 217 que contiene la página 215, ordenada en la lista de bancos 219, la información complementaria de banco 411 dentro del banco 217, el número de página 403 del documento y el número de documento 301 de la lista de documentos 225.

Sistema operativo I. Desarrollo global del proceso

El sistema 100 proporciona un procedimiento perfeccionado para indexar y buscar documentos en un sistema de almacenamiento y recuperación de información. El procedimiento incluye dos procesos básicos: indexación de un documento y búsqueda de un documento utilizando una solicitud de búsqueda.

Con referencia a la figura 7, se muestra un diagrama de flujo del procedimiento global según la presente invención. Un documento, o conjunto de documentos, se introduce 701 en el sistema 100. En el caso de documentos o imágenes impresos, los documentos pueden explorarse normalmente con el escáner, y procesarse mediante el módulo OCR 133 para producir los datos de texto del archivo de texto 207. O un documento con un archivo de imagen 209 puede importarse de otros sistemas, como por ejemplo una imagen facsímil, y procesarse por medio del módulo OCR 133. Alternativamente, el documento puede entrarse directamente como datos de texto en el archivo de texto 207, o el documento puede ser una imagen, para la cual el usuario ha proporcionado información de texto adicional en el archivo de texto 207. Cuando un documento se recibe directamente en forma de datos de texto, el archivo DFS 211 no proporciona ninguna correlación entre el archivo de texto 207 y el archivo de imagen 209. Alternativamente, cuando los datos de texto se reciben directamente pueden convertirse en un archivo de imagen utilizando técnicas convencionales de formación de imagen, y a continuación puede actualizarse el archivo DFS 211 para incluir la información de correlación imagen-texto. La subrutina de ejecución de aplicaciones 119 impulsa preferiblemente al usuario a seleccionar/crear un cajón 201 y una carpeta 203 para almacenar el/los documento(s) de entrada.

Después de obtener los datos de texto de un documento introducido, el documento introducido se indexa 703 a continuación. La indexación es gestionada por la subrutina de ejecución de indexaciones 121. La indexación se realiza preferiblemente página a página si el documento está siendo explorado durante la etapa de entrada 701. También puede realizarse por documentos o si se desea por grupos o en forma diferida, para manejar adecuadamente grandes cantidades de documentos. La indexación identifica todos los n-grams de cada página del documento, localiza el espacio disponible en uno o más de los bancos 217 del cajón y la carpeta seleccionados por el usuario, y actualiza correspondientemente el banco 217, el índice de banco 223, la lista de bancos 219, y la lista libre 221.

Una vez completada la indexación, el usuario podrá decidir transferir 705 un cajón 201 completo de documentos indexados 205 a otro ordenador, ya sea directamente a través de una conexión de red o a través de un soporte de almacenamiento portátil. Esto permitiría a otro ordenador buscar en los documentos 205 del cajón 201 sin necesidad de reindexar 703 los documentos. Alternativamente, el usuario puede decidir transferir uno o más documentos 205 o carpetas 203. Sólo es necesaria la reindexación cuando se han transferido documentos entre cajones 201.

El sistema 100 es capaz de buscar en cualquier cajón 201 indexado. La subrutina de ejecución de aplicaciones 119 impulsa al usuario a seleccionar cajón(es) 201, carpeta(s) 203 ó documento(s) 201 para buscar 709. El usuario entra 707 una solicitud de búsqueda, especificando las palabras deseadas y los operadores booleanos. El usuario también especifica un parámetro de coincidencia E que describe el porcentaje de exactitud entre la solicitud de búsqueda y las palabras presentes en cualquier documento. En la forma de realización preferida, E está limitado a un rango útil, como por ejemplo (20%-100%).

Con la entrada de la solicitud de búsqueda, la subrutina de ejecución de búsquedas 123 gestiona el proceso de búsqueda 709. Brevemente, la búsqueda implica la conversión de las palabras solicitadas en n-grams, y a continuación la comparación de estos n-grams de las palabras solicitadas con los n-grams de los índices del banco 223 para determinar el grado de coincidencia. Los documentos con coincidencias que satisfagan la solicitud de búsqueda y el parámetro de coincidencia se recuperan y se visualizan 711 para el usuario. El usuario puede realizar búsquedas adicionales, almacenar resultados de búsqueda, imprimir los documentos, copiar partes de los mismos en otro software de aplicación para utilizarlos en este último o finalizar la búsqueda.

II. Indexación de documentos

Con referencia a la figura 8, se muestra un diagrama de flujo del proceso 703 de indexación de un documento en el sistema 100, tal como es gestionado por la subrutina de ejecución de indexaciones 121. la subrutina de ejecución de indexaciones 121 realiza una serie de operaciones para indexar cada n-gram en cada página 215 del(de los)

\hbox{documento(s)}

205 introducido(s) por el usuario, y para actualizar el banco 217, la lista de bancos 219, la lista libre 221 y el índice de bancos 223 adecuados.

La subrutina de ejecución de indexaciones 121 asigna 801 memoria para el proceso de indexación. Esto implica limpiar las memorias intermedias 143, 145 y reservar cualesquiera otros recursos de memoria adicionales suficientes para permitir la indexación de un gran número de páginas.

La subrutina de ejecución de indexaciones 121 llama al módulo de referencia de documento 125 para obtener 803 un número de documento 301 para el documento 205 que está siendo indexado. la subrutina de ejecución de índices 121 proporciona el módulo 125 de referencia de documentos con un nodo raíz del cajón 201 que contiene el documento especificado 205, y un nombre de documento del documento 205, proporcionado por el usuario durante la etapa de entrada 701. El módulo de referencia del documento 125 abre la lista de documentos 225 para el cajón 201 y determina a partir del número 309 de entradas sin utilizar si existe espacio disponible para un nuevo documento en la lista de entradas existente 311. Si no es así, se crea una nueva entrada 311 al final de la lista de entradas del documento 225. Se fija el valor de estado 303 y se almacena el nombre de ruta completo 305 del documento. Si existe en la lista una entrada 311 sin utilizar, el módulo de referencia del documento 125 explora las listas y localiza la primera entrada 311 con un valor de estado 303 no fijado. Se fija el valor de estado 303 y se almacena el nombre de ruta completo. En ambos casos, el módulo de documentos de referencia 125 devolverá el número de documento 301 que es la posición de la entrada nueva/actualizada 311 de la lista de documentos 225.

La subrutina de ejecución de indexaciones 121 invoca el módulo de indexación de páginas 127 para indexar 805 cada página del documento 205 y almacena los datos resultantes en un índice de banco 223. El módulo de indexación de páginas 127 lleva a cabo la creación real del número de n-grams para cada página del documento. Con referencia a la figura 9, se muestra un diagrama de flujo del proceso de indexación de una página. Este proceso se repite para cada página del documento.

El módulo de indexación de páginas 127 obtiene primero una información complementaria de banco 411 para la página de algún banco 217. Ésta asocia la página que está siendo indexada con una posición en un banco 217 particular del cajón 201 de usuario seleccionado. Además, permite almacenar cada página del documento en un banco 217 diferente. Esto se realiza del modo siguiente:

El módulo de indexación de páginas 127 lee 901 la lista de bancos 219 e identifica el primer banco 217 listado en la misma que no está lleno leyendo el recuento de entradas libres de cada banco 217 hasta que obtiene 903 un valor distinto de cero. El módulo de indexación de páginas 127 disminuye 905 este recuento de entradas libres y abre 907 el banco 217 asociado.

El módulo de indexación de páginas 127 comprueba 909 el número 407 de entradas sin utilizar del banco 217. Este valor indica el lugar del que se han suprimido páginas que previamente habían sido indexadas e incluidas en el banco 217. Si este valor es distinto de cero, el módulo de indexación de páginas 127 cruza 911 las entradas del banco 217 e identifica la primera entrada con un valor de estado 405 que indica una entrada vacía. Si el número de entradas sin utilizar 407 es cero, el módulo de indexación de páginas 127 crea 913 a continuación una entrada nueva al final del banco 217, utilizando el número 401 de entradas del banco 217 para posicionar la última entrada.

En ambos casos, el módulo de indexación de páginas 127 fija 915 este valor de estado 405 para indicar una entrada actual y almacena el número de documento 301 a partir de la lista 225 de documentos en la entrada, y el número de páginas 403 del documento. A continuación incremente 917 el número 401 de entradas del banco 217, y obtiene 918 el número de banco del banco 217, y la información complementaria 411 de banco dentro del banco
217.

El módulo de indexación de páginas 127 carga 919 a continuación el archivo de palabras vacías 135 para filtrar las palabras vacías y evitar que sean incluidas en la claves de palabra generadas para la página. El módulo de indexación de páginas 127 crea 921 a continuación las claves de palabra para la página. Las claves de palabra se almacenarán en la clave de página 509 para la página del índice de banco 223 asociada con el banco 217 que contiene la página. Las claves de palabra para la clave de página 509 se crean todas primero, y a continuación se almacenan posteriormente en la clave de página 509, ya que se determina el tamaño de clave de página 513 para la clave de página 509 antes del almacenamiento real. Las claves de palabra se crean como sigue.

Con referencia a la figura 10, se muestra un diagrama de flujo del proceso de creación de las claves de palabra que constituyen la clave de página 509 de una página determinada. El tamaño de clave de página 513 se inicializa 1001 a cero, y se limpian las memorias intermedias 143, 145. La memoria intermedia de índice 143 se utilizará para almacenar la clave de página 509 cuando se esté creando. La memoria intermedia de página 145 se utiliza para soportar los datos de texto de la página. Se carga 1002 en la memoria intermedia de página 145. El módulo de indexación de páginas 127 realiza un bucle 1003 sobre todas las palabras de la página tal como están almacenadas en la memoria intermedia 145. El módulo de indexación de la página 127 determina 1005 si la palabra actual se encuentra al final del archivo. Si la palabra actual no se encuentra al final del archivo, comprueba 1007 si la palabra es una palabra vacía del archivo de palabras vacías 135. Esto puede hacerse por cálculo de la dirección informática o por otras técnicas convencionales. Si la palabra actual es una palabra vacía, la formación de bucle 1003 continua.

Si la palabra actual no es una palabra vacía, el módulo de indexación de páginas 127 comprueba 1009 la longitud de la palabra añadiendo "\sim" a la palabra hasta que su longitud es igual a la longitud de los n-gram. Por ejemplo, en la forma de realización preferida, se expanden las palabras de dos letras con un "\sim" para hacerlas de tres letras. Además, se prefiere que las palabras de una letra no se expandan porque aportan muy pocos datos identificables a la búsqueda.

El módulo de indexación de páginas 127 crea a continuación la clave de palabra para la palabra. Esto incluye la determinación 1011 del número k de n-grams de la palabra. El número k de n-grams para la clave de palabra es (longitud de la palabra - 2).

A continuación la palabra se descompone en sus n-grams y cada n-gram se lee desde la palabra, empezando con el primer carácter, y leyendo el número de caracteres necesario para crear el n-gram. Para cada n-gram se determina 1013 el número de n-gram. Esto puede hacerse consultando el número de n-gram en la tabla de consulta de n-grams 227 o calculando directamente el número de n-gram, como anteriormente.

En ambos casos, el resultado de las etapas 1011 y 1013 será la clave de palabra para la palabra, comprendiendo el número k y los números individuales de n-gram para cada uno de los n-grams de la palabra. La clave de palabra se añade a la memoria intermedia 143. El tamaño de la clave de página 513 se actualiza 1014 para acumular el tamaño de la clave de palabra. El nuevo tamaño de la clave de página 513 es:

tamaño de clave de página = tamaño de clave de página + (1+k* tamaño de (número de n-gram)).

La función tamaño de obtiene el número de bytes utilizado para almacenar el número de n-gram. En el caso de los trigrams son dos bytes, pero será superior para n-grams mayores. Este número se multiplica por k, el número de n-grams. Se añade un elemento extra para almacenar k.

Para cada número n-gram así generado e incluido en la clave de palabra debe actualizarse el mapa de entradas de n-grams 505 y el mapa de páginas de índices 507. El número de n-gram se utiliza como un índice en los mapas de entrada de n-gram 505. Se obtiene 1015 y comprueba 1017 el valor de índice en el mapa de entradas de n-grams 505. Si el valor del índice es cero, significa que el n-gram no dispone de una referencia previa en el banco 217 y debe crearse un nuevo mapa de páginas de índices 507 para el n-gram. Si el valor de índice no es cero, significa que se ha encontrado previamente el n-gram en una página del banco 217, y que ya existe un mapa de páginas de índices 507 para el n-gram. El (valor del índice - 1) del mapa de entradas de n-grams 505 se añade a continuación a la posición del índice 501 para obtener el mapa de páginas de índices correcto 507.

Por consiguiente, si el valor del índice del mapa de entradas de n-grams 505 es cero, se añade 1019 otro mapa de páginas de índices 507 al final de la serie actual de mapas de páginas de índices 507. El valor de índice del mapa de entradas de n-grams 505 referenciado por el número de n-gram se actualiza 1021 con la posición del nuevo mapa de páginas de índices 507, de modo que puede accederse directamente al último utilizando el mapa de entradas de n-grams 505 cuando se crea (durante la indexación) o se identifica (durante la búsqueda) otra referencia para el n-gram. Así, en el caso del primer n-gram de la primera página que debe incluirse en un banco 217, este n-gram (cualquiera que sea su número de n-gram) tendrá un número de índice de 1 en el mapa de entradas de n-grams 505, y el primer mapa de páginas de índices 507 se asociará con él. El n-gram siguiente, de nuevo sin considerar su número de n-gram, o lo "lejos" que esté del primer n-gram, tendrá el valor de índice 2 en su mapa de entradas de n-grams 505, y se asignará al segundo mapa de páginas de índices 507.

Si el valor de índice del mapa de entradas de n-grams 505 es distinto de cero, el módulo de indexación de páginas 127 utiliza el (valor de índice - 1) para obtener 1023 el mapa de páginas de índices 507 para el n-gram.

El módulo de indexación de páginas 127 fija 1025 la (información complementaria de banco 411)^{avo} bit del mapa de páginas de índices 507 para el n-gram. Esto indica que la (información complementaria de banco 411)^{ava} entrada del banco 217 dispone de una referencia para el n-gram. Esta es la página que está siendo indexada actualmente.

Esta actualización se repite (1013) para cada n-gram de la clave de palabra. El módulo de indexación de páginas 127 continúa (1033) con la siguiente palabra disponible de la página.

Una vez completadas en bucle 1003 todas las claves de palabra para la página, todo el conjunto de claves de palabra para la página constituirá la clave de página completa 509. El tamaño de la clave de página 513 será el tamaño de toda la clave de página 509, y estará presente en la memoria intermedia 143. Ahora queda almacenar esta clave de página 509 en una ubicación adecuada de la tabla de claves de página 517 del índice de banco 223.

El módulo de indexación de páginas 127 cruza 1027 la lista libre 221 para el banco 217 para determinar 1029 la posición 511 de clave de página de la primera clave de página disponible 509 con un tamaño de clave de página 513 superior o igual al tamaño de clave de la página de la clave de página acabada de completar. Como se ha establecido anteriormente, las lista libre 221 mantiene las compensaciones 511 de las claves de página 509 de la páginas que han sido suprimidas, y así tiene su espacio disponible para almacenar otra clave de página 509 para otra página.

Si dicha posición de clave de página se localiza 511, la clave de página recientemente creada se escribe 1031 para la entrada de clave de página 509 de la tabla de claves de página 517. Si no se encuentran entradas intersticiales de tamaño suficiente, la clave de página se escribe 1033 después de la última entrada existente en la tabla de claves de página 517. En ambos casos, la posición de clave de página 511, y el tamaño de clave de página 513, se actualizan.

Con referencia de nuevo a la figura 9, el módulo de indexación de páginas 127 descarga 923 luego el archivo de palabras vacías 135, y devuelve 925 el control a la subrutina de ejecución de índices 121.

Con referencia de nuevo a la figura 8, la subrutina de ejecución de índices 121 actualiza 807 el archivo DFS 211 con la referencia de banco (número de banco 409 y información complementaria de banco 411) de la página indexada, asociando la referencia de banco con la imagen particular y la página de texto de la página indexada. Esto permite al sistema 100 recuperar la información del índice para la página durante la búsqueda y cuando se visualiza y correlaciona la imagen de la página con los datos de texto para acceso por el usuario. Similarmente, la subrutina de ejecución de índices 121 actualiza 809 el archivo DFS 211 con el número de documento 301 a partir de la lista de documentos 225, permitiendo nuevamente al sistema 100 recuperar el documento. Finalmente, la subrutina de ejecución de índices 121 libera 811 los recursos de memoria asignados. A continuación, la subrutina de ejecución de índices 121 devuelve el control a la subrutina de ejecución de aplicaciones 119 para permitir la indexación adicional, la transferencia 705 de índices o documentos, o la búsqueda 709.

III. Búsqueda de documentos

Con referencia de nuevo a la figura 7, el usuario también puede buscar 709 en cualquier número de cajones documentos que coincidan con una solicitud de búsqueda entrada. Generalmente, la búsqueda implica la descomposición de cada palabra de la solicitud de búsqueda en sus n-grams, la determinación de cuáles páginas del documento incluyen qué n-grams, y finalmente la realización de alguna operación booleana u otras operaciones en las coincidencias resultantes. Más particularmente, se busca en cada banco para determinar su algunos n-grams de las palabras solicitadas aparecen en alguna página del banco. Estas páginas se anotan. A continuación, se comparan para cada página los n-grams de las palabras solicitadas con cada n-gram de cada clave de palabra de cada clave de página de la página. Esto determina la precisión de la coincidencia entre las palabras solicitadas y las palabras de cada página.

Con referencia a la figura 11, se muestra un diagrama de flujo del proceso 709 de búsqueda del sistema 100 con una solicitud de búsqueda entrada, que gestiona la subrutina de ejecución de búsquedas 123.

La subrutina de ejecución de búsquedas 123 empieza asignando 1101 suficientes recursos de memoria para utilizar durante la búsqueda. Esto incluye limpiar la memoria intermedia 145 de página y la memoria intermedia de búsqueda 143. Normalmente, se asignan aproximadamente 700k para la búsqueda en un cajón que contiene 16.000 documentos, Además, la subrutina de ejecución de búsquedas 123 inicializa una memoria intermedia de resultados que rastrea para cada banco qué entrada de página 413 (con información complementaria de banco 411) incluye un acierto para las palabras solicitadas.

La subrutina de ejecución de búsquedas 123 inicia a continuación un bucle 1103 sobre todos los cajones 201 seleccionados para la búsqueda, y a continuación un segundo bucle 1105 para todos los bancos 217 de cada cajón 201.

La subrutina de ejecución de búsquedas 123 recupera 1107 el índice de bancos 223 para el banco actual 217 y a continuación invoca el módulo de ejecución de búsquedas 129 para realizar una operación de procesamiento previo 1109. La operación de procesamiento previo 1109 identifica las páginas del interior del banco actual 217 en las que coinciden algunos n-grams de las palabras de la solicitud de búsqueda que satisfacen el parámetro de coincidencia. Por lo tanto, el procesamiento previo es una primera etapa de filtrado que elimina de la búsqueda posterior las páginas que no contienen ningún n-gram de las palabras buscadas. La figura 12 es un diagrama de flujo de la operación de procesamiento previo.

El módulo de ejecución 129 inicializa una serie de listas de marcas de página, que rastrean para cada página del banco 217 si la página incluye un acierto o cualquier n-gram de cualquier palabra solicitada, calificando la página para posterior procesamiento. En la forma de realización preferida, la serie de listas marcadas de página es un aserie 1-D con una entrada para cada página del banco 217, correspondiente a su información complementaria de banco 411. Es decir, listas de marcas de página [P_{max}], donde P_{max} es el número máximo de páginas del banco 217.

El módulo de ejecución de búsquedas 129 inicia a continuación un bucle 1203 sobre cada palabra Q de la solicitud de búsqueda. El módulo de ejecución de búsquedas 129 también inicializa 1204 una serie de contadores G de coincidencia de n-grams. La serie de contador G de coincidencia de n-grams rastrea en la página el número de veces que se encuentra algún n-gram de una palabra buscada en la página. Es decir, G[P] es el número de presencias de un n-gram de cualquier palabra solicitada en la página P del banco 217. Otro bucle 1205 se ha iniciado sobre cada n-gram de la palabra solicitada actual Q. Los n-grams de la palabra solicitada actual Q se determinan del modo descrito anteriormente durante la indexación.

El módulo de ejecución 129 determina 1207 si el n-gram actual de Q está presente en alguna página del banco 217 tomando el número de n-gram y comprobando el valor del índice del mapa de entradas de n-grams 505 para este número de n-gram del índice del banco 223. Como se ha descrito anteriormente, el mapa de entradas de n-grams 505 indica para un número de n-gram determinado, y por lo tanto n-gram determinado, si existe alguna presencia del n-gram en el banco 217.

Si el valor del índice es cero, significa que no existían ocurrencias de este n-gram de la palabra solicitada Q en ninguna de las páginas de este banco 217. En este caso, el bucle 1205 continúa.

Si el valor del índice es distinto de cero, significa que existe por lo menos una ocurrencia de n-gram de la palabra solicitada Q en alguna página del banco 217, y el valor del índice indica el índice para el mapa de páginas de índices 507 que identifica la(s) página(s) del banco 217 con presencia. Consiguientemente, el módulo de ejecución de búsquedas 129 cruza el mapa de páginas de índices 507 (añadiendo el (valor de índice - 1) a la posición de índice 501 para el índice de banco 223).

A continuación, el módulo de ejecución de búsquedas 129 efectúa un bucle 1209 sobre el mapa de páginas de índices 507, leyendo cada bit B del mapa de páginas. El módulo de ejecución de búsquedas 129 determina 1211 si el bit para cada página está fijado. En caso contrario, el bucle 1209 continúa.

Si el bit está fijado, esto indica que la página incluye el n-gram de la palabra buscada Q en algún lugar de los datos de texto. El módulo de ejecución de búsquedas 129 incrementa 1213 el contador de coincidencias n-gram G[P]. Esto indica que un n-gram de la palabra buscada Q aparece en la página P del banco 217.

A continuación, el módulo de ejecución de búsquedas 129 comprueba 1215 si el recuento incrementado G[P] es suficiente para considerar que la página contiene un acierto para la palabra buscada actualmente Q. Comprueba si el G[P] es igual o superior al número de n-grams de la palabra buscada Q, al ponderarlo mediante el parámetro de coincidencia E introducido por el usuario. Si el usuario desea una coincidencia exacta entre una solicitud de búsqueda Q y una palabra de una página, cada n-gram de la palabra solicitada Q debe estar presente en la página, y por lo tanto debe fijarse un bit para la página en cada mapa de páginas de índices 507 para cada uno de los n-grams de la palabra solicitada Q. Por ejemplo, si la palabra solicitada es "doorknob", existen seis n-grams, y debe fijarse el mismo bit de página en los seis mapas de página de índice 507 para los n-grams de "doorknob". Si el usuario desea una coincidencia menos que exacta, debe fijarse pocos (algún porcentaje) de los mapas de página de índice 507. En consecuencia, la comprobación 1215 es:

G[P]\leq\frac{K_{Q}*E}{100}

donde K_{Q} es el número de n-grams en Q, y E es el parámetro de coincidencia. E es preferiblemente un valor entre un límite inferior útil, como 20 y 100.

Si esta comprobación 1215 se satisface, a continuación se actualiza 1217 la serie de listas marcadas de página para mostrar que esta página incluye un acierto para la palabra solicitada Q. Es decir, la serie de listas de páginas se fija en [Q, B], donde B es el índice de la página actual, controlado por bucle 1209. El procesamiento continúa hasta que el bucle 1209 está agotado. Una vez completados todos los bucles, el procesamiento previo 1109 (figura 11) está realizado.

Con referencia de nuevo a la figura 11, el procesamiento previo 1109 produce por lo tanto la serie de listas de página, que muestra para cada palabra solicitada Q la página del banco 217 que está siendo procesado actualmente contiene un ejemplo de la palabra solicitada. No indica en qué lugar de la página se produce la coincidencia entre la palabra solicitada Q y alguna palabra. Pero cada página del banco 217 puede procesarse 1111 para seguir determinando las coincidencias exactas entre las palabras solicitadas y las palabras de una página, y si satisface algunos operadores booleanos.

Con referencia a la figura 13, se muestra un diagrama de flujo del procesamiento 1111 de un banco 217. En esta fase, sólo las páginas que se seleccionaron durante el procesamiento previo 1109 vuelven a procesarse. El módulo de ejecución de búsquedas 129 inicia un bucle 1301 sobre cada entrada de página 413 del banco 217, iterando mediante los valores de información complementaria del banco 411. Un segundo bucle 1303 se inicia sobre cada palabra solicitada Q de la solicitud de búsqueda.

El módulo de ejecución de búsquedas 129 comprueba 1305 si la página presenta un ejemplo de la palabra solicitada Q. Esto se realiza preferiblemente comprobando la serie de listas de página en [Q, información complementaria de banco 411]. Este valor se fijará durante el procesamiento previo 1109 en el caso de que hubiere algún ejemplo de la palabra solicitada Q en la página, según se determine en el mapa de páginas de índices 507. Si la página no se ha indicado de este modo, el bucle 1303 continúa.

En caso contrario, la clave de página 509 para la página se carga 1307 en la memoria intermedia de página 143. Esto se realiza utilizando la información complementaria de banco 411 para indexar en la tabla de compensaciones de clave de página 515 y obtener la posición de clave de página real 511 para la clave de página correcta 509. La clave de página 509 se procesa 1309 a continuación para determinar cuántos de los n-grams de la página coinciden con las palabras solicitadas. La figura 14 es un diagrama de flujo de este proceso 1309.

El módulo de ejecución de búsquedas 129 inicializa un contador de coincidencias de clave de palabra para cada clave de palabra W de la clave de palabra 509 respecto a cada palabra solicitada Q. Esto es preferiblemente una serie 2D [Q_{n}, W_{n}] siendo Q_{n} el número de palabras solicitadas Q, y W_{n} el número de claves de palabra W de la clave de página 509.

El módulo de ejecución de búsquedas 129 inicia una serie de bucles. Un bucle exterior 1403 itera sobre cada n-gram de una palabra solicitada Q actual (que está controlada por el bucle 1303, véase la figura 13). Los n-grams se determinan igual que anteriormente, junto con el número de n-gram utilizado realmente en las comparaciones. Un segundo bucle 1405 itera sobre cada clave de palabra W de la clave de página 509 para la página. Como se ha descrito anteriormente, durante la indexación cada palabra produce una clave de palabra (y por lo tanto cada palabra) con cada palabra solicitada. Un buclefinal 1407 itera sobre cada n-gram de una clave de palabra.

En el centro de este bucle, el módulo de ejecución de búsquedas 129 compara 1409 el n-gram actual de la palabra solicitada Q con el n-gram actual de la clave de palabra. Si son los mismos, el contador de coincidencia de claves de palabra se incrementa 1411 (por lo tanto aumenta la serie de contador de coincidencia de claves de palabra [Q, W] para las iteraciones actuales de Q y W). Lo que significa esto es que un n-gram de la palabra solicitada Q coincide con un n-gram de una palabra de la página. El contador rastreará el número de estas coincidencias.

El módulo de ejecución de búsquedas 129 determina 1413 a continuación si existen suficientes coincidencias (utilizando el valor de la serie de contador de coincidencia de claves de palabra [Q, W] para indicar la coincidencia entre la propia palabra solicitada Q y la propia palabra. de nuevo, esta comprobación se basa en el parámetro de coincidencia E. Por lo tanto si se requiere una coincidencia exacta (E=100), cada n-gram de la clave de palabra W debe coincidir con cada n-gram de la palabra solicitada Q; es decir:

serie de contador de coincidencia de claves de palabra [Q, W] = K_{Q}

donde K_{Q} es el número de n-grams de la palabra solicitada Q. Si no se requiere una coincidencia exacta (E<100), debe coincidir algún porcentaje. Generalmente:

serie de contador de coincidencia de claves de palabra [Q, W] \geq \frac{K_{Q} *E}{100}

Si esta comprobación se satisface, el módulo de ejecución de búsquedas 129 fija 1414 la memoria intermedia de resultados para el banco y la entrada de página 411 indicando un acierto para la solicitud de búsqueda. El bucle interior 1407 no necesita completarse, ya que coinciden suficientes n-grams.

El módulo de ejecución de búsquedas 129 continúa agotando bucles 1405 y 1403, completando la evaluación anterior para cada palabra de cada clave de palabra W, y para cada clave de palabra W de la clave de página actual 509 (en la forma controlada por bucle 1301, véase figura 13).

Con referencia de nuevo a la figura 13, la entrada de página actual 413 se procesa 1309 para cada palabra solicitada Q. Una vez todas las palabras solicitadas han sido analizadas, en la forma descrita, el módulo de ejecución de búsquedas 129 determina 1313 si la solicitud de búsqueda incluye algunas operaciones booleanas. Si se requiere una operación booleana, el módulo de ejecución de búsquedas 129 realiza el procesamiento booleano 1315. El procesamiento booleano 1315 puede realizarse de forma convencional, ya que en este punto el módulo de ejecución de búsquedas 129 ha identificado si la palabra solicitada Q es un acierto para la página actual. Sólo necesitan identificarse las condiciones erróneas en la memoria intermedia de resultados, ya que las páginas que satisfacen la solicitud booleana se devolverán al usuario. El procesamiento booleano 1315 se realiza generalmente del modo siguiente:

Si la palabra solicitada Q es un argumento para una operación AND, y no existe un ejemplo de la palabra solicitada Q en la página (en la forma determinada por el contador de coincidencia de claves de palabra) la página se marca como rechazada.

Si la palabra solicitada Q es un argumento para una operación NOT, y existe un ejemplo de la palabra solicitada Q en la página, la página se marca como rechazada.

Si algunos pares de palabras solicitadas Q_{1}, Q_{2} son argumentos para una operación XOR, y si sólo ambas o ninguna de ellas se encuentra en la página, la página se marca como rechazada.

Si la palabra solicitada Q es una frase (secuencia de palabras entre comillas) y no se encuentra la misma secuencia, la página se marca como rechazada.

Después del procesamiento booleano 1315, el módulo de ejecución de búsquedas 129 continúa.

Si no se requiere el procesamiento booleano 1315 el módulo de ejecución de búsquedas 129 continúa para completar el bucle 1301, iterando para la siguiente entrada de página 413 del banco 217. Una vez efectuado, el módulo de ejecución de búsquedas 129 devuelve el control a la subrutina de ejecución de búsquedas 123.

Con referencia de nuevo a la figura 11, la subrutina de ejecución de búsquedas 123 invoca el módulo de listas de búsqueda 131 para consolidar 1113 los resultados de los procesos de búsqueda. La consolidación de los resultados de búsqueda se utiliza porque las páginas de un documento determinado pueden residir en bancos múltiples 217. El módulo de listas de búsquedas 131 revisa la memoria intermedia de resultados e identifica el banco 217 recién procesado. Se determina la entrada de página 413 por el banco 217 y la información complementaria de banco 411 de cada acierto y el módulo de listas de búsquedas 131 accede al número de documento 403 para obtener el documento que contienen la entrada de página 413. A partir de aquí, puede accederse al archivo DFS 211, y se accede a las páginas restantes del documento, que se consolidan. La lista consolidada de documentos que coinciden con la solicitud de búsqueda se devuelve a la subrutina de ejecución de búsquedas 123.

A continuación, la subrutina de ejecución de búsquedas 123 completa 1115 los bucles 1105, 1103 sobre cada banco y cada cajón, cerrando los cajones y bancos adecuados. Los resultados de todos los bancos y cajones se consolidan de forma similar y se desarrolla la lista final de documentos que coinciden con la solicitud de búsqueda 1117 y dicha lista se visualiza 711 (figura 7) para el usuario para su evaluación. A continuación, la subrutina de ejecución de búsquedas 123 desasigna la memoria utilizada durante la búsqueda y devuelve 1119 el control a la subrutina de ejecución de aplicaciones 119.

El procedimiento de descomposición en n-grams según la presente invención ha sido descrito respecto a sistemas de información y recuperación. No obstante, muchas otras utilizaciones de la descomposición en n-grams se encuentran dentro del ámbito de la presente invención según la reivindicaciones, La descomposición en n-grams puede utilizarse con otros procedimientos de procesamiento de texto o sistemas para perfeccionar la calidad de los mismos. Por ejemplo, podría utilizarse la descomposición en n-grams con un revisor de ortografía, tanto por lotes como interactivo, para identificar palabras mal escritas, y proporcionar una lista más exacta de posibles substituciones para cada una. Igualmente, los n-grams pueden utilizarse con diccionarios o tesauros informáticos para identificar raíces de palabras y consultar la definición adecuada o sinónimos, antónimos o similares. Los n-grams también pueden utilizarse par los revisores gramaticales de forma similar, para identificar palabras antes del análisis gramatical. Estas y otras utilizaciones de la descomposición en n-grams para el procesamiento de datos de texto se encuentran comprendidas en el ámbito de la presente invención según la reivindicaciones.

Claims (11)

1. Memoria legible por ordenador que incluye una estructura de almacenamiento para la indexación de documentos (205) mediante n-grams, presentando cada documento (205) un número de documento y un nombre de documento y por lo menos una página (215), presentando cada página (215) un número de página, que comprende:

un banco (217) que comprende una lista de entradas de página (413), identificando cada entrada de página (413) una página (215) mediante el número de documento del documento (205) que contiene la página (215), y un número de página dentro del documento (205); y

un índice de banco (223) asociado con el banco (217) que comprende:

i)

una pluralidad de mapas de entradas de n-grams (505), estando asociado cada mapa de entradas de n-grams (505) a un único n-gram, teniendo por lo menos un mapa de entradas de n-grams (505) un índice para un mapa de entradas de índices (507) donde por lo menos una página (215) identificada en el banco (217) incluye el n-gram asociado con el mapa de entradas de n-grams (505); y

ii)

una pluralidad de mapas de entradas de índices (507), estando indexado cada mapa de entradas de índices (507) por uno de los mapas de entradas de n-grams (505), presentando cada mapa de entradas de índices (507) una pluralidad de posiciones, correspondiendo cada posición a una entrada de página (413) del banco (217), e indicando cada posición si la entrada de página (413) correspondiente del banco (217) identifica o no una página (215) que contiene el n-gram asociado con el mapa de entradas de n-grams (505) que indexa el mapa de entradas de índices (507).

2. Memoria legible por ordenador según la reivindicación 1, en la que:

a)

cada entrada de página (413) del banco (217) presenta una información complementaria (411);

b)

cada mapa de entradas de índices (507) incluye una pluralidad de posiciones de bit, estando asociada cada posición de bit con una entrada de página (413) del banco (217), presentando cada posición de bit un primer valor cuando la página (215) identificada en la entrada de página (413) asociada con la posición de bit incluye el n-gram asociado con el mapa de entradas de n-grams (505) que indexa el mapa de entradas de índices (507), y un segundo valor cuando la página (215) identificada en la entrada de página (413) asociada con la posición de bit no incluye el n-gram asociado con el mapa de entradas de n-grams (505) que indexa el mapa de entradas de índices (507).

3. Memoria legible por ordenador según la reivindicación 1 ó 2, que comprende además:

a)

un cajón (201) que incluye:

i)

una lista de documentos (225), identificándose cada documento (205) de forma exclusiva en la lista;

ii)

una pluralidad de bancos (217), e índices (223) de banco asociados; y

iii)

una lista de bancos (219) que incluye para cada uno de una pluralidad de bancos (217) un recuento de un número de entradas de página vacías (413) del banco (217).

4. Memoria legible por ordenador según una de las reivindicaciones 1 a 3, en la que cada banco (217) comprende además:

a)

una tabla de claves de página (517) que incluye por lo menos una clave de página (509), estando cada clave de página (509) asociada exclusivamente con una entrada de página (413) del banco (217), y que comprende:

b)

para cada palabra de la página (215) una lista de los n-gram de la palabra.

5. Procedimiento implementado por ordenador para la recuperación de un documento (205), que comprende:

a)

almacenamiento de la estructura de almacenamiento según la reivindicación 1 en una memoria legible por ordenador;

b)

recepción de un término solicitado; y

c)

para cada uno de los n-grams del término solicitado:

i)

determinación, a partir del mapa de entradas de n-grams (505) del índice de banco asociado con el n-gram del término solicitado, de si existe un mapa de entradas de índices (507) para el n-gram;

ii)

determinación, conforme a un mapa de entradas de índices (507) existente, del mapa de entradas de índices (507) de cada entrada de página (413) del banco (217) que identifica una página (215) que contiene el n-gram asociado con el mapa de entradas de índices (507); y

iii)

incremento de un contador de n-grams para cada página (215) que contiene el n-gram;

d)

determinación, para cada página (215) del banco (217) de si el contador de n-grams para la página (215) está suficientemente cerca del número de n-grams del término solicitado para indicar que la página (215) contiene el término solicitado; y

e)

recuperación, conforme el contador de n-grams para una página (215) está suficientemente próximo al número de n-grams del término solicitado, del documento (205) que contiene la página (215) para el posterior análisis de la solicitud.

6. Procedimiento implementado por ordenador según la reivindicación 5, en el que el contador de n-grams para la página (215) está suficientemente cerca del número de n-grams del término solicitado cuando

G[P] \frac{K*E}{100}

donde

P es la página (215)

G es el contador de coincidencias de n-grams para la página P;

K es el número de n-grams del término solicitado; y

E es un parámetro de coincidencia seleccionado para controlar el porcentaje de coincidencias entre G y K.

7. Procedimiento implementado por ordenador para indexar una pluralidad de documentos almacenados por n-grams, que comprende:

(a)

almacenamiento de la estructura de almacenamiento de la reivindicación 1 en una memoria legible por ordenador;

(b)

recepción de la página actual para ser indexada;

(c)

creación de una entrada para la página actual en la lista de páginas indexadas;

(d)

almacenamiento para cada palabra no vacía de la página actual de una lista de n-grams de la palabra; y

(e)

para cada n-gram, actualización, en el mapa de entradas de índices (507) asociado con el n-gram, de la entrada para la página actual para indicar que la página actual incluye el n-gram.

8. Procedimiento según la reivindicación 7 que comprende el almacenamiento, para una palabra no vacía de la página actual, de una lista de n-grams de la palabra mediante:

iii.1)

determinación de un número de n-grams para cada n-gram de la palabra;

iii.2)

almacenamiento del número de n-grams de cada n-gram de la palabra; y

iii.3)

asociación de los números de n-gram con la página actual.

9. Procedimiento según la reivindicación 7, que comprende:

recepción de una palabra solicitada, y

para cada uno de un número de n-grams del término solicitado:

determinación de si existe un mapa de entradas de índices (507) asociado con el n-gram; y

conforme al mapa de entradas de índices (507) existente,

determinación del mapa de entradas de índices (507) de cada página (215) de la lista de páginas indexadas que contienen el n-gram asociado con el mapa;

para cada página (215) de la lista de páginas indexadas, determinación de si la página (215) contiene un número suficiente de n-grams del término solicitado para indicar que la página (215) contiene el término solicitado; y

conforme a una página (215) que contiene el término solicitado, recuperación del documento (205) que contiene la página (215) para posterior análisis de la solicitud.

10. Procedimiento según la reivindicación 9, que comprende la determinación de si una página (215) contiene un número suficiente de n-grams del término solicitado mediante la ecuación:

G[P]=\frac{K*E}{100}

en la que

P es la página (215);

G es el número de n-grams del término solicitado contenido en la página P;

K es el número de n-grams del término solicitado; y

E es un parámetro de coincidencia seleccionado para controlar el porcentaje de coincidencias entre G y K.

11. Memoria legible por ordenador que incluye un programa que configura y controla un procesador para ejecutar las etapas previstas en las reivindicaciones 5 a 10.