Algorytm do znalezienia wspólnych edycje

Question

Mam dwie listy słów, przykład:

list 1 list 2 

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

chciałbym znaleźć

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

To powinno być uporządkowane według ilości zdarzeń, tak Mogę filtrować te, które nie pojawiają się często.

Listy obecnie składają się z 35 tys. Słów, obliczenia powinny zająć około 6h na przeciętnym serwerze.

Answer 1

Moim ostatecznym rozwiązaniem jest użycie mosesdecodera. Podzielałem słowa na pojedyncze znaki i używałem ich jako korpusów równoległych, a następnie użyłem modelu wyodrębnionego . Porównałem Sursilvana i Valladera.

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

Można użyć algorytmów edycji odległości, na przykład Levenshtein distance. Może być konieczne wprowadzenie niewielkich zmian w algorytmach rejestracji dokładnych modyfikacji.

Answer 3

Edycja algorytmów odległości i metoda Levenshteina, podobnie jak metoda LCS, są korzystne. Ale są one używane do zmiany jednego słowa na drugie, dzięki tym metodom można dowiedzieć się, jak zmienić jedno słowo na inne z minimalną ilością zmian. Ale nie są one przydatne, aby znaleźć minimalną ilość zmian w dwóch słownikach.

najdłuższy wspólny podciąg (LCS) problemem jest znalezienie najdłuższy podciąg wspólny dla wszystkich sekwencji w zbiorze sekwencji (często tylko dwa). Należy zauważyć, że podsekwencja różni się od podciągu, patrz podłańcuch pod względem podciągania. Jest to klasyczny problem z informatyką, oparty na programach do porównywania plików, takich jak diff, i ma zastosowania w bioinformatyce .

Korzystając LCS ani innych metod, dla każdego słowa w listy1, okaże się, że, jak to słowo zmienia się na inną listy 2. na przykład między kolana & stóp: LCS = FT, różnica = oo = > ee. Powinieneś zrobić dwuczęściowy wykres, który pierwsza część tworzy ze słów różnicowych, a druga część tworzy z listy1. Każdy węzeł w drugiej części jest połączony z własną powiązaną różnicą w pierwszej części.

Przypuszczam, że długość i całkowita część słów są ograniczone.

Możemy modelować ten problem za pomocą wykresów. Przydziel każdą zmianę do jednego węzła. np. e → i (która określa jedną ze zmian) to etykieta dla jednego węzła. na przykład, jeśli cała operacja formularza p → q jest ustawiona na jedną część na wykresie dwudzielnym, a różnica całkowita dla każdej pary słów jest równa jednej i zdefiniowanie kolekcji Edge, która Edge uv łączy wierzchołek U z V, jeśli słowo (u) (w drugiej części) dla zmiany na poprawne słowo wymaga zmian V.Masz maksymalnie 25 * 26 węzeł w pierwszej części (dla tego przykładu). jeśli w Twoim przypadku długość> = 1, więc musisz ustawić limit. Zakładam, że maksymalna część zmian dla każdego słowa jest równa 3. i dlatego mamy 3 * 35K maksymalny węzeł w pierwszej części. Teraz możesz rozwiązać problem, wybierając zestaw węzłów w pierwszej części, które mogą być pokryte maksymalnym słowem w drugiej części (twoja wybrana powinna nastąpić zmiana słowa na poprawne słowo).

Znajdź minimalne cięcie wierzchołków na tym wykresie, aby znaleźć zestaw węzłów, do których mogą dostarczyć twoje żądanie. Następnie powtórz wycinanie algorytmów wierzchołkowych, aż uzyskasz dobrą odpowiedź.

możesz użyć pewnego rodzaju ograniczeń, aby zmniejszyć rozmiar wykresu, np. Usunąć wszystkie węzły w pierwszej części, które mają stopień 1, ponieważ węzły te są połączone z dokładnie jednym słowem, więc wydają się być bezużyteczne.

Ta symulacja wykresu może rozwiązać problem. W bieżącym opisie problemu, granice algorytmu działają poprawnie.

na przykład:

jest przykładem granice na wykresie (usunięcie wszystkich węzłów w ramach operacji, które mają 1 EDGE)

1-usunąć węzeł 4, ponieważ jest to związane tylko (Nod), a następnie usunąć węzeł (nod) 2-usuń węzeł 2, ponieważ jest on podłączony tylko do (sghoul), a następnie usuń węzeł (sghoul) 3-teraz usuń węzeł 3, ponieważ jest tylko podłączony do (goud) [sghoul jest usuwany ostatni krok], a następnie usuń węzeł (goud)

a teraz masz jedną operację oo => ee i możesz wybrać to.

Będę więcej myślał i spróbuję edytować ten tekst.