Domanda Un algoritmo per trovare modifiche comuni


Ho due liste di parole, un esempio:

 list 1  list 2

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

Mi piacerebbe trovare

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

Questo dovrebbe essere ordinato in base alla quantità di occorrenze, quindi posso filtrare il file quelli che non appaiono spesso.

Le liste attualmente consistono in 35k parole, il calcolo dovrebbe prendi circa 6 ore su un server medio.


10
2018-05-19 14:11


origine


risposte:


Modifica gli algoritmi di distanza e la distanza di Levenshtein come LCS il metodo è utile Ma sono usati per cambiare una parola in un'altra, con questi metodi puoi scoprire come cambiare una parola in un'altra parola con una quantità minima di modifiche. Ma non sono utili per trovare la quantità minima di modifiche in due dizionari.

Il più lungo problema di sottosuccessione (LCS) è quello di trovare il più lungo   sottosequenza comune a tutte le sequenze in un insieme di sequenze (spesso solo   Due). Si noti che la sottosequenza è diversa da una sottostringa, vedere   sottostringa vs. sottosequenza. È un classico problema di informatica,   la base dei programmi di confronto di file come diff e has   applicazioni in bioinformatica.

Usando LCS o qualsiasi altro metodo, per ogni parola in list1, trova che questa parola cambia in un'altra nell'elenco 2. per esempio, tra piedi e piedi: LCS = FT, difference = oo => ee. Dovresti creare un grafico bipartito che la prima parte faccia da parole diverse, e la seconda parte da lista1. Ogni nodo nella seconda parte è collegato alla propria differenza correlata nella prima parte.

Suppongo che la lunghezza e la parte totale delle parole siano limitate.

Possiamo modellare questo problema con i grafici. Assegna ogni modifica a un nodo. per esempio e → i (che determina una delle modifiche) è l'etichetta per un nodo. ad esempio, se tutte le operazioni del modulo p → q sono impostate su una parte nel grafico bipartito e la differenza totale per ogni coppia di parole è uguale a una e definisce Edge quella raccolta Edge uv collega vertice U a V se word (u) (nella seconda parte) per la modifica della parola corretta ha bisogno delle modifiche di V. Hai un massimo 25 * 26 nodi nella prima parte (per questo esempio). se nel tuo caso lunghezza> = 1 , quindi è necessario impostare un limite. Assumerò che la parte massima del cambiamento per ogni parola è uguale a 3.e quindi abbiamo il nodo massimo 3 * 35K nella prima parte. Ora puoi risolvere il problema scegliendo l'insieme di nodi nella prima parte che può essere coperto con la parola massima nella seconda parte (la tua scelta dovrebbe avvenire con la modifica della parola per correggere la parola).

Trova il taglio vertice minimo in questo grafico, per trovare un insieme di nodi che possono fornire la tua richiesta.e ripetere l'algoritmo del vertice tagliato fino a ottenere una buona risposta.

è possibile utilizzare una sorta di limiti per ridurre la dimensione del grafico, ad esempio rimuovere tutti i nodi nella prima parte con gradi 1, perché questi nodi sono collegati esattamente a una parola, quindi sembrano essere inutili.

Questa simulazione grafica può risolvere il tuo problema. Con la corrente affermazione del problema, questo limite dell'algoritmo funziona correttamente.

per esempio:enter image description here

È un esempio di limiti in questo grafico (rimuovere tutti i nodi nella parte operazione che hanno 1 bordo):

1-rimuovi il nodo 4 perché è solo collegato a (annuisci), quindi rimuovi   node (nod) 2-rimuove il nodo 2 perché è solo connesso a   (sghoul), quindi rimuovi il nodo (sghoul) 3-ora rimuovi il nodo 3 perché lo è   solo collegato a (goud) [sghoul viene rimosso l'ultimo passaggio], quindi rimosso   nodo (goud)

e ora hai una operazione oo => ee e puoi scegliere questo.

Ci penserò di più e cercherò di modificare questo testo.


10
2018-05-24 23:22



È possibile utilizzare gli algoritmi di modifica della distanza, ad esempio Distanza Levenshtein. Potrebbe essere necessario apportare alcune modifiche minori negli algoritmi per registrare le modifiche esatte.


3
2018-05-19 14:31



La mia soluzione finale è usare il decodificatore di file. Ho diviso le parole in singoli personaggi e li utilizza come corpus parallelo e utilizza il modello estratto. Ho confrontato Sursilvan e 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

2
2018-06-05 12:03