Алгоритм поиска общих прав

Ответ 1

Моим окончательным решением является использование mosesdecoder. Я разделил слова на одиночные символы и использовали их в качестве параллельного корпуса и использовали извлеченной модели. Я сравнил Сурсиллан и Валладера.

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

Изменить дистанционные алгоритмы и расстояние Левенштейна как Метод LCS полезен. Но они используются, чтобы изменить одно слово на другое, этими методами вы можете узнать, как изменить одно слово на другое слово с минимальным количеством изменений. Но они не могут найти минимальное количество изменений в двух словарях.

Самая длинная проблема с общей подпоследовательностью (LCS) - найти самый длинный подпоследовательность, общая для всех последовательностей в наборе последовательностей (часто просто два). Обратите внимание, что подпоследовательность отличается от подстроки, см. подстрока и подпоследовательность. Это классическая проблема компьютерных наук, в основе программ сравнения файлов, таких как diff, и приложений в биоинформатике.

Используя LCS или любые другие методы, для каждого слова в списке1 найдите, как это слово изменяется на другое в списке 2. например, между ногой и ногами: LCS = FT, разность = oo = > ee. Вы должны сделать двудольный граф, который первая часть делает из разностных слов, а вторая - из списка1. Каждый node во второй части связан со своей собственной разницей в первой части.

Я предполагаю, что длина и общая часть слов ограничены.

Мы можем моделировать эту проблему с графами. Назначьте каждое изменение на один node. например, e → i (который определяет одно из изменений) является меткой для одного node. например, если вся операция формы p → q установлена ​​на одну часть в двудольном графе, а общая разница для каждой пары слов равна единице и определяет коллекцию Edge, что Edge uv связывает вершину U с V если слово (u) (во второй части) для изменения правильного слова требует V изменений. У вас есть максимум 25 * 26 node в первой части (для этого примера). если в вашем случае длинa >= 1, поэтому вам нужно установить лимит. Я предполагаю, что максимальная часть изменения для каждого слова равна 3. и поэтому у нас есть 3 * 35K максимум node в первой части. Теперь вы можете решить проблему, выбрав в первой части набор node, который может быть покрыт максимальным словом во второй части (на ваш выбор должен произойти смена слова для правильного слова).

Найдите минимальный разрез вершины на этом графике, чтобы найти набор из node, чтобы они могли предоставить ваш запрос. И повторите результирующий алгоритм вершин, пока не получите хороший ответ.

вы можете использовать некоторую оценку для уменьшения размера графика, например, удалить все узлы в первой части, которая имеет степень 1, потому что эти узлы связаны ровно с одним словом, поэтому они кажутся бесполезными.

Это графическое моделирование может решить вашу проблему. С текущим оператором проблемы эта граница алгоритма работает правильно.

например:

Это пример для границ в этом графе (удалите все node в рабочей части, что они имеют 1 ребро):

1-remove node 4, потому что он подключен только к (кивок), затем удаляет node (кивок) 2-remove node 2, поскольку он подключен только к (sghoul), затем удалите node (sghoul) 3-now remove node 3, потому что это только подключен к (goud) [sghoul удален последний шаг], затем удалите node (Goud)

и теперь у вас есть одна операция oo = > ee, и вы можете выбрать это.

Я подумаю больше и попытаюсь отредактировать этот текст.

Ответ 3

Вы можете использовать алгоритмы редактирования расстояния, например расстояние Левенштейна. Может потребоваться внести некоторые незначительные изменения в алгоритмы для регистрации точных изменений.