Subcadenas a juego de un diccionario a otra cadena: ¿sugerencias?

Question

Gente Hellow Stack Overflow. Me gustaría recibir algunas sugerencias sobre el siguiente problema. Estoy usando Java.

Tengo una matriz n. ° 1 con varias cadenas. Por ejemplo, dos de las cadenas podrían ser: "Una manzana cayó sobre la cabeza de Newton" y "Las manzanas crecen en los árboles".

Por otro lado, tengo otro array # 2 con términos como (Fruits => Apple, Orange, Peach; Items => Pen, Book; ...). Yo llamaría a esta matriz mi "diccionario".

Al comparar elementos de una matriz a la otra, necesito ver en qué "categoría" caen los elementos del # 1 de # 2. P.ej. Ambos del # 1 caerían bajo "Fruits".

Mi consideración más importante es la velocidad. Necesito hacer esas operaciones rápido. Una estructura que permita la recuperación de tiempo constante sería buena.

Consideré un Hashset con el método contains(), pero no permite subcadenas. También he intentado correr como expresiones regulares (manzana | naranja | melocotón | ... etc) con la caja de la bandera insensible, pero leí que no va a ser rápido cuando los términos aumentan en número (mínimo 200 es de esperar). Finalmente, busqué y estoy considerando usar una ArrayList con indexOf() pero no sé sobre su rendimiento. También necesito saber cuál de los términos realmente coincide, por lo que en este caso, sería "Apple".

Proporcione sus opiniones, ideas y sugerencias sobre este problema.

Vi el algoritmo Aho-Corasick, pero es muy probable que las palabras clave/términos cambien con frecuencia. Entonces no creo que pueda usar eso. Oh, no soy un experto en minería de textos y matemática, así que por favor elabore conceptos complejos.

¡Gracias, gente de Stack Overflow, por su tiempo! :)

Answer 1

¿Funcionaría un suffix tree o una estructura de datos similar para su aplicación? Ofrece O (m) cadena de búsqueda, donde m es la longitud de la cadena de búsqueda, después de una O (n) - o mejor con un poco de engaño - configuración inicial, y, con un poco de esfuerzo extra, puede asociar datos arbitrarios, como una referencia a una categoría, con palabras completas en su diccionario. Si no desea codificarlo usted mismo, creo que la biblioteca BioJava incluye una implementación.

También puede agregar cadenas a un árbol de sufijo después de la configuración inicial, aunque el costo seguirá siendo O (n). Probablemente no sea un gran problema si agrega palabras cortas.

Answer 2

Si utiliza un multimapa de Google Collections, tienen una función para invertir el mapa (para que pueda comenzar con un mapa como {"Fruits" => [Apple]}, y producir un mapa con {"Apple" => ["Fruits"]}. Así que puedes buscar la palabra y encontrar una lista de categorías para ella, en una llamada al mapa.

Esperaría que quisiera dividir las cadenas y buscar el palabras en el mapa de a una por vez, de modo que pueda hacer derivaciones (ajuste para diferentes terminaciones de palabras) y filtrado de palabras prohibidas. Usar el mapa debería tener buenos tiempos de búsqueda, además es fácil de probar.

Answer 3

Si tiene solo 200 términos para buscar, las expresiones regulares podrían funcionar para usted. Por supuesto, la expresión egular es grande, pero si la compila una vez y solo utiliza este Patrón compilado, el tiempo de búsqueda es probablemente lineal en la longitud combinada de todas las cadenas en el arreglo # 1 y no veo cómo puede esperar ser mejor que eso .

Así que el algoritmo sería: concatenar las palabras de la matriz # 2 que desea buscar en la expresión regular, compilarla, y luego encontrar las coincidencias en la matriz # 1.

(Las expresiones regulares se compilan en una máquina de estados, es decir, en cada carácter de la cadena solo hace una búsqueda de tablas para el siguiente estado. Si la expresión regular es complicada, puede tener retroceso que aumente el tiempo, pero la expresión regular tiene una estructura muy simple.)