Algoritmo eficiente de codificación de palabras

Question

Estoy buscando un algoritmo eficiente para codificar un conjunto de letras en una permutación que contiene el número máximo de palabras.

Por ejemplo, digamos que me da la lista de letras: {e, e, h, r, s, t}. Necesito ordenarlos de tal manera que contengan la cantidad máxima de palabras. Si ordeno esas letras en "theres", contienen las palabras "the", "there", "her", "here", y "ere". Entonces ese ejemplo podría tener una puntuación de 5, ya que contiene 5 palabras. Quiero ordenar las letras de tal manera que tenga el puntaje más alto (contiene la mayoría de las palabras).

Un algoritmo ingenuo sería intentar y puntuar cada permutación. Creo que esto es O (n!), Por lo que se probarán 720 permutaciones diferentes solo para las 6 letras anteriores (incluidos algunos duplicados, ya que el ejemplo tiene e dos veces). Para más letras, la solución ingenua se vuelve rápidamente imposible, por supuesto.

El algoritmo no tiene que producir realmente la mejor solución, pero debería encontrar una buena solución en un tiempo razonable. Para mi aplicación, simplemente adivinar (Monte Carlo) a unos pocos millones de permutaciones funciona bastante mal, por lo que actualmente es la marca a vencer.

Actualmente estoy usando el algoritmo Aho-Corasick para anotar permutaciones. Busca cada palabra en el diccionario en una sola pasada a través del texto, por lo que creo que es bastante eficiente. Esto también significa que tengo todas las palabras almacenadas en un trie, pero si otro algoritmo requiere un almacenamiento diferente, eso también está bien. No estoy preocupado por configurar el diccionario, solo el tiempo de ejecución del pedido y la búsqueda real. Incluso un diccionario difuso podría usarse si fuera necesario, como un Bloom Filter.

Para mi aplicación, la lista de letras dada es de aproximadamente 100 y el diccionario contiene más de 100.000 entradas. El diccionario nunca cambia, pero se deben ordenar varias listas de letras diferentes.

Estoy pensando en probar path finding algorithm. Creo que podría comenzar con una carta al azar de la lista como punto de partida. Entonces, cada letra restante se usaría para crear un "camino". Creo que esto funcionaría bien con el algoritmo de puntuación Aho-Corasick, ya que los puntajes se pueden construir una letra a la vez. Aunque aún no he intentado encontrar ruta; tal vez ni siquiera es una buena idea? No sé qué algoritmo de búsqueda de ruta podría ser el mejor.

Otro algoritmo en el que pensé también comienza con una letra al azar. Luego se buscará en el diccionario trie las ramas "ricas" que contengan las letras restantes. Las ramas de diccionario que contienen letras no disponibles se eliminarán. Estoy un poco confuso sobre los detalles de cómo funcionaría esto exactamente, pero podría eliminar por completo las permutaciones de puntuación.

Answer 1

Puede probar simulated annealing, que se ha utilizado con éxito para problemas complejos de optimización en varios dominios. Básicamente, realiza escalada aleatoria mientras reduce gradualmente la aleatoriedad. Como ya tienes el puntaje de Aho-Corasick, ya has hecho la mayor parte del trabajo. Todo lo que necesitas es una forma de generar permutaciones vecinas; para eso, algo tan simple como intercambiar un par de letras debería funcionar bien.

Answer 2

¿Has pensado en usar un algoritmo genético? Ya tienes los comienzos de tu función de acondicionamiento físico. Podría experimentar con los algoritmos de mutación y cruce (gracias Nathan) para ver cuál hace el mejor trabajo.

Otra opción sería que su algoritmo cree la palabra más pequeña posible del conjunto de entrada, y luego agregue una letra a la vez para que la nueva palabra también sea o contenga una palabra nueva. Comience con algunas palabras iniciales diferentes para cada conjunto de entrada y vea a dónde conduce.

Solo unos pocos pensamientos ociosos.

Answer 3

Podría ser útil para comprobar cómo otros han resuelto esto: http://sourceforge.net/search/?type_of_search=soft&words=anagram

En esta página usted puede generar anagramas en línea. He jugado con eso por un tiempo y es muy divertido.No explica en detalle cómo hace su trabajo, pero los parámetros dan una idea. http://wordsmith.org/anagram/advanced.html

Answer 4

He aquí una idea, inspirada en Markov Chains:

1. calcular previamente la carta probabilidades de transición en su diccionario. Cree una tabla con la probabilidad de que una letra X sea seguida por otra letra Y, para todos los pares de letras, según las palabras del diccionario.
2. Genere permutaciones seleccionando al azar cada letra siguiente del grupo de letras restante, según la letra anterior y la tabla de probabilidades, hasta que todas las letras se hayan agotado. Ejecuta esto muchas veces.
3. Puede experimentar aumentando la "memoria" de su tabla de transición; no mire solo una letra hacia atrás, sino diga 2 o 3. Esto aumenta la tabla de probabilidades, pero le da más posibilidades de crear una palabra válida.