Algoritmo de empaque de texto

Apuesto a que alguien ha resuelto esto antes, pero mis búsquedas han quedado vacías.Algoritmo de empaque de texto

Quiero incluir una lista de palabras en un búfer, haciendo un seguimiento de la posición inicial y la longitud de cada palabra. El truco es que me gustaría empacar el buffer de manera eficiente eliminando la redundancia.

Ejemplo: casa de muñeca dollhouse

Estos se pueden embalar en el búfer simplemente como dollhouse, recordando que doll es cuatro letras a partir de la posición 0, dollhouse es nueve letras en 0, y house es de cinco letras en 3.

Lo que he encontrado hasta el momento es:

Ordenar las palabras más larga a la más corta: (casa de muñecas, casa, muñeca)
Escanee el búfer para ver si la cadena ya existe como una subcadena, de ser así, tenga en cuenta la ubicación.
Si no existe, agréguelo al final del búfer.

Dado que las palabras largas a menudo contienen palabras más cortas, esto funciona bastante bien, pero debería ser posible hacerlo mucho mejor. Por ejemplo, si extiendo la lista de palabras para incluir ragdoll, mi algoritmo aparece con dollhouseragdoll que es menos eficiente que ragdollhouse.

Este es un paso de preprocesamiento, por lo que no estoy muy preocupado por la velocidad. O (n^2) está bien. Por otro lado, mi lista real tiene decenas de miles de palabras, por lo que O (n!) Probablemente esté fuera de discusión.

Como nota al margen, este esquema de almacenamiento se utiliza para los datos en la tabla `nombre 'de una fuente TrueType, cf. http://www.microsoft.com/typography/otspec/name.htm

Fuente

2009-05-10 Adrian McCarthy

¿No puedes simplemente usar algo como gzip? – Zifre

Lo que está describiendo es lo que hacen todos los algoritmos de compresión, excepto que está agregando la restricción de mirar palabras de texto plano como los elementos que se comprimen en lugar de bits. –

No es exactamente lo mismo que los algoritmos de compresión, porque cada palabra debe mantener su "palabrería". Como dije en otro comentario, no se puede combinar "lawman" y "woman", pero en compresión, estaría bien comprimir "man" juntos porque no es necesario mantener un buffer consistente. –

Este es el problema de supercuerdas más corto: encuentre la cadena más corta que contiene un conjunto de cadenas como subcadenas. De acuerdo con this IEEE paper (que puede que no tenga acceso a desafortunadamente), la solución de este problema es exactamente NP-complete. Sin embargo, las soluciones heurísticas están disponibles.

Como primer paso, debe encontrar todas las cadenas que son subcadenas de otras cadenas y eliminarlas (por supuesto, de todos modos, todavía necesita registrar sus posiciones relativas a las cadenas que las contienen). Estas cadenas totalmente contenidas se pueden encontrar de manera eficiente usando un generalised suffix tree.

Luego, fusionando repetidamente las dos cadenas que tienen la superposición más larga, se garantiza que producirá una solución cuya longitud no sea inferior a 4 veces la longitud mínima posible. Debería ser posible encontrar los tamaños de superposición rápidamente usando dos árboles radix como sugiere un comentario de Zifre en Konrad Rudolph's answer. O bien, es posible que pueda usar el árbol de sufijo generalizado de alguna manera.

Lo siento, no puedo encontrar un enlace decente para usted; no parece haber una página de Wikipedia ni ninguna información públicamente accesible sobre este problema en particular. Se menciona brevemente here, aunque no se proporcionan soluciones sugeridas.

Fuente

2009-05-10 14:54:06

Gracias! Tener un nombre para el problema siempre es un gran comienzo. Pensé que una solución perfecta podría estar fuera de tu alcance, pero una buena solución sería satisfactoria. –

Creo que puede usar un Radix Tree. Cuesta algo de memoria debido a los punteros a hojas y padres, pero es fácil hacer coincidir cadenas (O (k) (donde k es el tamaño de cadena más largo).

Fuente

2009-05-10 13:28:00 Qubeuc

Creo que solo funciona con cadenas que comienzan con subcadenas comunes. Las cadenas que terminan con subcadenas comunes no serán reconocidas. Corrígeme si estoy equivocado. – Zifre

Si las cadenas terminan con una subcadena común, no se emparejarán de todos modos según esta descripción. Si lo hace, las cuerdas individuales se desordenarán. –

Para elaborar, si tuvieras "mujer" y "legislador", no puedes combinarlos aunque quisieras. La única forma en que la combinación funciona (según entiendo el problema) es si un sufijo de una palabra coincide con un prefijo de otra. –

Lo primero que pienso es: utilizar una estructura de datos para determinar los prefijos y sufijos de sus cadenas comunes. a continuación, ordenar las palabras bajo consideración de estos prefijos y sufijos. Esto daría lugar a su deseado ragdollhouse.

Fuente

2009-05-10 13:31:58

Lo que está sugiriendo suena como que podría implementarse con un árbol de doble raíz (uno hacia adelante y hacia atrás).Esto funcionaría en la mayoría de los casos, pero si las cadenas tienen partes comunes en el medio, pero no en los bordes, no funcionará. – Zifre

Por ejemplo, no reconocería el consumo y la suma. – Zifre

tiene una apariencia similar a la Knapsack problem, que es NP-completo, por lo que no es una algoritmo "definitivo"

Fuente

2009-05-10 13:48:07

¿Podría explicarnos el vínculo con el problema Knapsack? – akappa

El problema de Knapsack (empaquetar de manera óptima algunas mercancías en una bolsa) se parecía a mí. De hecho (vea la respuesta de j_random_hacker) este es un problema de NP completo, como el de Knapsack. –

Sí, pero todavía no puedo ver la similitud de ese problema con el KP. 3-SAT es NPC, pero definitivamente no puedo decir que sea similar a ese problema de "empaquetado de cuerdas". – akappa

Hice un laboratorio en la universidad donde nos encargamos de implementar un programa de compresión simple.

Lo que hicimos fue aplicar secuencialmente estas técnicas al texto:

BWT (Burrows-Wheeler transform): ayuda a las cartas de reabastecimiento en secuencias de cartas idénticas (Pista * hay sustituciones matemáticos para conseguir las letras en lugar de realmente hacer las rotaciones)
MTF (Move to front transform): Reescribe la secuencia de letras como una secuencia de índices de una lista dinámica.
Huffman encoding: Una forma de codificación de la entropía que construye una tabla de códigos de longitud variable en la que se les da códigos más cortos a los símbolos encontradas frecuentemente y los códigos más largos son dados a encontrado poca frecuencia símbolos

Aquí, he encontrado el assignment page.

Para recuperar el texto original, usted hace (1) decodificación de Huffman, (2) MTF inverso, y luego (3) BWT inverso. Hay varios recursos buenos en todo esto en Interwebs.

Fuente

2009-05-10 14:05:11

Interesante, pero bastante irrelevante para la pregunta en cuestión. Además, es habitual poner un paso de Codificación de Longitud de Ejecución antes del MTF. :) –

No volvería a inventar esta rueda una vez más. Ya ha pasado una gran cantidad de mano de obra en algoritmos de compresión, ¿por qué no tomar uno de los ya disponibles?

Estas son algunas buenas opciones:

gzip para la compresión rápida/velocidad de descompresión
bzip2 para una compresión amarga poco, pero mucho más lento de descompresión
LZMA de relación de compresión muy alta y descompresión rápida (más rápido que bzip2 pero más lento que gzip)
lzop para una compresión/descompresión muy rápida

Si usa Java, gzip is already integrated.

Fuente

2009-05-10 15:10:25 martinus

No estoy después de empacar, no compresión. En tiempo de ejecución, quiero que el texto completo de cada palabra sea fácilmente accesible. Podría hacerlo sin ningún tipo de embalaje, pero reconocí que el embalaje podría darme una reducción significativa de la huella y una localidad de referencia mejorada. –

¿En qué se diferencia su embalaje y desembalaje de cualquier otro algoritmo de compresión y descompresión? – martinus

Con la compresión, debe descomprimir. Con el embalaje como he descrito, no es necesario desempacar. Tengo el texto completo de las palabras originales directamente disponibles. –

No está claro qué es lo que quieres hacer.

¿Desea una estructura de datos que le permita almacenar de forma consciente las cadenas mientras permite operaciones como la búsqueda posible en un período de tiempo razonable?

¿Simplemente desea una matriz de palabras, comprimida?

En el primer caso, puede elegir un patricia trie o un String B-Tree.

Para el segundo caso, sólo puede adoptar algunas techinique compresión de índice, al igual que:

Si usted tiene algo así como:

aaa 
aaab 
aasd 
abaco 
abad

Puede comprimir así:

0aaa 
3b 
2sd 
1baco 
2ad

El número es la longitud del prefijo común más grande con la cadena anterior. Puede modificar ese esquema, por ej. la planificación de un "reinicio" del prefijo común después de sólo K palabras, para una reconstrucción rápida

Fuente

2009-05-10 15:23:01 akappa

Tenga en cuenta que, con el último esquema, debe comprimir mucho más que un embalaje como ha sugerido. Por supuesto, no puede tener un solo puntero a la palabra, sino una tupla (puntero a la primera palabra con prefijo 0, desplazamiento) – akappa

No estoy buscando un método de compresión. Necesito un acceso aleatorio rápido al texto completo de cada palabra, por lo que no quiero descomprimir sobre la marcha. El embalaje reduce la huella de memoria y mejora la localidad de referencia. –

¿Estás seguro de que mejora la localidad? La localidad depende en gran medida del orden en el que solicite palabras, no solo de la huella de memoria (excepto casos límite, por supuesto). ¿Y está seguro de que mejora en gran medida la huella de memoria? Me parece que esta optimización puede ser algo bueno si tienes un conjunto particular de cadenas, pero es prácticamente inútil en, por ejemplo, palabras en lenguaje natural. – akappa

paso Refinar 3.

Mire a través de la lista actual y ver si alguna palabra en la lista comienza con un sufijo de la palabra actual. (Es posible que desee mantener el sufijo más largo que alguna longitud, más de 1, por ejemplo).
En caso afirmativo, agregue el prefijo distinto a esta palabra como prefijo de la palabra existente y ajuste todas las referencias existentes (¡lento!)
En caso negativo, agregue la palabra al final de la lista como en el paso 3 actual.

Esto le daría 'ragdollhouse' como los datos almacenados en su ejemplo. No está claro si siempre funcionaría de manera óptima (si también tenía 'barbiedoll' y 'dollar' en la lista de palabras, por ejemplo).

Fuente

2009-05-10 15:45:40

Respuesta

Cuestiones relacionadas