Que la estructura proporciona los mejores resultados de rendimiento; trie (prefijo de árbol), sufijo de árbol o el sufijo de la matriz? Hay otras estructuras similares? ¿Cuáles son las buenas implementaciones de Java de estas estructuras?
Edit: en este caso quiero hacer cadena de coincidencia entre una gran diccionario de nombres y un gran conjunto de textos en lenguaje natural, con el fin de identificar los nombres de los diccionario de textos.
El TRIE fue la primera estructura de datos de este tipo descubierto.
El sufijo árbol es una mejora sobre el TRIE ( tiene un sufijo de enlaces que permiten a los lineales de error de búsqueda, el sufijo árbol adornos innecesarios ramas de la TRIE por lo tanto no requiere mucho espacio ).
El sufijo de la matriz es una versión reducida de la estructura de datos basada en el sufijo árbol (sin sufijo enlaces (lento error partidos), sin embargo, la coincidencia de patrones es muy rápido).
El TRIE no es para uso en el mundo real, ya que consume demasiado espacio.
El sufijo árbol es más ligero y más rápido que el Trie y se utiliza para el índice de ADN o optimizar algunos de los grandes motores de búsqueda web.
El sufijo de la matriz es más lento en algunos patrón de búsquedas que el sufijo árbol, pero utiliza menos espacio y es más extendido que el Sufijo árbol.
En la misma familia de estructuras de datos:
Existen otras implementaciones, la CST es una aplicación del Sufijo árbol mediante un sufijo de la matriz y algunas otras estructuras de datos para obtener algunas de las Sufijo árbol de capacidades de búsqueda.
El FCST va más allá, se implementa una muestra de sufijo árbol con un sufijo de la matriz.
El DFCST es una versión dinámica de la FCST.
Expansión:
Los dos factores importantes son el uso del espacio y de la operación el tiempo de ejecución. Se podría pensar que con modernas máquinas, esto no es importante pero para el índice de ADN de un solo ser humano que necesitaría 40 gigabytes de memoria (mediante un sin comprimir y unoptimized sufijo de árbol). Y para construir uno de estos índices por encima de esta cantidad de datos que puede tomar días. Imaginar Google, que tiene un montón de búsquedas de datos, se necesita un gran índice de todos los datos de la web y que no cambie cada vez que alguien construye una página web. Disponen de algún tipo de almacenamiento en caché para que. Sin embargo, el índice principal es, probablemente, la estática. Y cada par de semanas o así que se reúnen todos los nuevos sitios web y datos y crear un nuevo índice, en sustitución de la antigua, cuando el nuevo está terminado. No sé el algoritmo que se utiliza para el índice, pero es probablemente un sufijo de la matriz con el sufijo árbol de propiedades a través de una base de datos con particiones.
El CST usos de 8 gigabytes, sin embargo, el sufijo árbol de operaciones de la velocidad se reduce considerablemente.
El Sufijo de la matriz puede hacer lo mismo en unos 700 megas a 2 Gigas. Sin embargo, usted no va a encontrar errores genéticos en el ADN con un sufijo de la matriz (es decir: la búsqueda de un patrón con un comodín es mucho más lento).
El FCST (completamente comprimido sufijo árbol) puede crear un sufijo árbol en 800 1,5 gigas. Con una pequeña velocidad de deterioro hacia el CST.
El DFCST utiliza un 20% más de espacio que el FCST, y pierde velocidad a la estática de la aplicación de la FCST. (sin embargo, un índice dinámico es muy importante)
No hay muchos viable (espacio sabio) de las implementaciones del sufijo árbol porque es muy duro para realizar las operaciones de aumento de la velocidad de compensar las estructuras de datos ram costo de espacio.
Esto dijo el sufijo árbol tiene muy interesantes los resultados de la búsqueda por coincidencia de patrón con errores. Aho corasick no es tan rápido (aunque casi igual de rápido para algunos operatons, no de error de coincidencia) y la boyer moore se dejó en el polvo.
Qué operaciones qué piensas hacer? libdivsufsort en un tiempo fue el mejor sufijo de la matriz de implementación en C.
El uso de Árboles de Sufijos puede escribir algo que coincidirá con su diccionario a su texto en O(n+m+k) tiempo donde n es cartas en su diccionario, m es cartas en su texto, y k es el número de partidos. Intenta están mucho más lento para esto. No estoy seguro de qué es un Sufijo de la Matriz, por lo que no puedo comentar sobre eso.
Dicho esto, es no trivial, el código y no me enterado de cualquier bibliotecas de Java que proporcionan las funciones necesarias.
EDIT: En este caso quiero hacer cadena de coincidencia entre una gran diccionario de nombres y un gran conjunto de el lenguaje natural de los textos, con el fin de identificar los nombres de los diccionario de textos.
Esto suena como una aplicación para el algoritmo de Aho-Corasick: construir un autómata del diccionario (en el tiempo lineal), el cual puede ser utilizado para encontrar todas las ocurrencias de cualquiera de las palabras del diccionario en varios textos (también en el tiempo lineal).
(La descripción en estas notas de la conferencia, enlazado desde "enlaces Externos" de la sección de la página de la Wikipedia, es mucho más fácil de leer que la descripción en la página en sí.)
Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.
