Un algoritmo para encontrar ediciones comunes

Question

Tengo dos listas de palabras, un ejemplo:

list 1 list 2 

foot fuut 
barj kijo 
foio fuau 
fuim fuami 
kwim kwami 
lnun lnun 
kizm kazm 

Me gustaría encontrar

o → u # 1 and 3 
i → a # 3 and 7 
im → ami # 4 and 5 

Esto debe ser ordenada por cantidad de ocurrencias, por lo Puedo filtrar los que no aparecen a menudo.

Las listas constan actualmente de 35k palabras, el cálculo debería tomar alrededor de 6 horas en un servidor promedio.

Answer 1

Mi solución final es usar el codificador de moses. Dividí las palabras en caracteres individuales y las usé como corpus paralelo y utilicé el modelo extraído. Comparé a Sursilvan y a Vallader.

export IRSTLM=$HOME/rumantsch/mosesdecoder/tools/irstlm 
export PATH=$PATH:$IRSTLM/bin 

rm -rf corpus giza.* model 
array=("sur" "val") 
for i in "${array[@]}"; do 
    cp "raw.$i" "splitted.$i" 
    sed -i 's/ /@/g' "splitted.$i" 
    sed -i 's/./& /g' "splitted.$i" 
    add-start-end.sh < "splitted.$i" > "compiled.$i" 
    build-lm.sh -i "compiled.$i" -t ./tmp -p -o "compiled.lm.$i" 
    compile-lm --text yes "compiled.lm.$i.gz" "compiled.arpa.$i" 
done 

../scripts/training/train-model.perl --first-step 1 --last-step 5 -root-dir . -corpus splitted -f sur -e val -lm 0:3:$PWD/compiled.arpa.sur -extract-options "--SentenceId" -external-bin-dir ../tools/bin/ 

$HOME/rumantsch/mosesdecoder/scripts/../bin/extract $HOME/rumantsch/mosesdecoder/rumantsch/splitted.val $HOME/rumantsch/mosesdecoder/rumantsch/splitted.sur $HOME/rumantsch/mosesdecoder/rumantsch/model/aligned.grow-diag-final $HOME/rumantsch/mosesdecoder/rumantsch/model/extract 7 --SentenceId --GZOutput 

zcat model/extract.sid.gz | awk -F '[ ][|][|][|][ ]' '$1!=$2{print $1, "|", $2}' | sort | uniq -c | sort -nr | head -n 10 > results 

Answer 2

Puede usar los algoritmos de distancia de edición, por ejemplo, Levenshtein distance. Puede ser necesario hacer algunos cambios menores en los algoritmos para registrar modificaciones exactas.

Answer 3

Editar algoritmos de distancia y Levenshtein distancia como LCS método son beneficiosos. Pero se usan para cambiar una palabra por otra, con estos métodos puede averiguar cómo cambiar una palabra por otra con un mínimo de cambios. Pero no son útiles para encontrar la cantidad mínima de cambios en dos diccionarios.

La subsecuencia común (LCS) más larga problema es encontrar el subsecuencia común más larga de todas las secuencias en un conjunto de secuencias (a menudo sólo dos). Tenga en cuenta que la subsecuencia es diferente de una subcadena, vea subcadena contra subsecuencia. Es un problema clásico de informática, , la base de programas de comparación de archivos como diff, y tiene aplicaciones en bioinformática.

Mediante el uso de LCS o cualquier otro método, para cada palabra en lista1, encontramos que la forma en que las palabra cambia a otro en la lista 2. por ejemplo, entre el pie pies &: LCS = FT, diferencia = oo = > ee. Debe hacer un gráfico bipartito que la primera parte hace con palabras diferentes, y la segunda parte con la lista1. Cada nodo en la segunda parte está conectado a su propia diferencia relacionada en la primera parte.

Supongo que la longitud y la parte total de las palabras son limitadas.

Podemos modelar este problema con gráficos. Asigna cada cambio a un nodo. Por ejemplo, e → i (que determina uno de los cambios) es la etiqueta de un nodo. por ejemplo, si toda la operación del formulario p → q está configurada en una parte en gráfico bipartito y la diferencia total para cada par de palabras es igual a uno y define la colección Edge que Edge uv conecta el vértice U a V si la palabra (u) (en la segunda parte) para cambiar a la palabra correcta necesita cambios de V. Tiene un máximo de 25 * 26 nodos en la primera parte (para este ejemplo). if En su caso length> = 1, por lo que necesita establecer un límite. Asumiré que la máxima parte del cambio en cada palabra es igual a 3. y por lo tanto tenemos un nodo máximo de 3 * 35K en la primera parte. Ahora puedes resolver el problema eligiendo el conjunto del nodo en la primera parte que puede cubrirse con la palabra máxima en la segunda parte (tu elección debería ocurrir, cambiar la palabra por la palabra correcta).

Encuentra el corte de vértice mínimo en este gráfico, para encontrar el conjunto de nodos que pueden suministrar a tu solicitud. Y repite el algoritmo de corte de vértices hasta obtener una buena respuesta.

puede utilizar algún tipo de límites para reducir el tamaño del gráfico, por ejemplo, eliminar todos los nodos en la primera parte que tiene grado 1, porque estos nodos están conectados exactamente a una palabra, por lo que parecen ser inútiles.

Esta simulación de gráfico puede resolver su problema. Con el enunciado del problema actual, estos límites del algoritmo funcionan correctamente.

por ejemplo:

Es ejemplo para límites en este gráfico (eliminar todo el nodo en operación parte que tienen 1 borde):

1-eliminar nodo 4 porque es sólo conectado (asentir), luego eliminar el nodo (asentimiento) 2-eliminar el nodo 2 porque solo está conectado a (sghoul), luego quitar el nodo (sghoul) 3-ahora eliminar el nodo 3 porque es solo conectado a (goud) [sghoul se elimina último paso], luego eliminar el nodo (goud)

y ahora tiene una operación oo => ee y puede elegir esto.

Voy a pensar más y tratar de editar este texto.