Я работаю над проектом по построению высокоточного выравнивания слов между предложениями и их переводами на другие языки для измерения качества перевода. Я знаю о Giza++ и других инструментах выравнивания слов, которые используются как часть процесса статистического машинного перевода, но это не то, что мне нужно. Я ищу алгоритм, который может отображать слова из исходного предложения в соответствующие слова в целевом предложении, прозрачно и точно с учетом этих ограничений:
- два языка не имеют одинакового порядка слов, и порядок постоянно меняется
- некоторые слова в исходном предложении не имеют соответствующих слов в целевом предложении, и наоборот
- иногда слово в исходном коде соответствует нескольким словам в целевом, и наоборот, может быть сопоставление «многие ко многим».
- могут быть предложения, в которых одно и то же слово используется несколько раз, поэтому выравнивание необходимо выполнять со словами и их индексами, а не только со словами.
Вот что я сделал:
- Начните со списка пар предложений, скажем, английский-немецкий, где каждое предложение разбито на слова.
- Индексируйте все слова в каждом предложении и создайте инвертированный индекс для каждого слова (например, слово «мир» встречается в предложениях № 5, 16, 19, 26 и т. д.) как для исходных, так и для целевых слов.
- Теперь этот инвертированный индекс может предсказать корреляцию между любым исходным словом и любым целевым словом, как пересечение между двумя словами, разделенными их объединением. Например, если тагретное слово "Welt" встречается в предложениях 5, 16, 26, 32, Соотношение между (мир, Welt) есть количество индексов в пересечении (3), деленное на количество индексов в союзе ( 5), и, следовательно, корреляция равна 0,6. Использование союза дает более низкую корреляцию с часто встречающимися словами, такими как «the», и соответствующими словами в других языках.
- Снова выполните итерацию по всем парам предложений и используйте индексы для исходных и целевых слов для заданных пар предложений, чтобы создать матрицу корреляции.
Вот пример корреляционной матрицы между английским и немецким предложением. Мы видим проблемы, о которых говорилось выше.
На изображении есть пример выравнивания между английским и немецким предложением, показывающий корреляции между словами, а зеленые ячейки — это правильные точки выравнивания, которые должны быть идентифицированы алгоритмом выравнивания слов.
Вот кое-что из того, что я пробовал:
- В некоторых случаях возможно, что предполагаемое выравнивание — это просто пара слов с наивысшей корреляцией в соответствующем столбце и строке, но во многих случаях это не так.
- Я пробовал такие вещи, как алгоритм Дейкстры, чтобы нарисовать путь, соединяющий точки выравнивания, но, похоже, он не работает таким образом, потому что кажется, что вы можете переходить назад и вперед к более ранним словам в предложении из-за порядка слов, и там нет разумного способа пропустить слова, для которых нет выравнивания.
- Я думаю, что оптимальное решение будет включать в себя что-то вроде расширяющихся прямоугольников, которые начинаются с наиболее вероятных соответствий, охватывают соответствия многие ко многим и пропускают слова без выравнивания, но я не совсем уверен, что было бы хорошим способом реализовать это
Вот код, который я использую:
import random
src_words=["I","know","this"]
trg_words=["Ich","kenne","das"]
def match_indexes(word1,word2):
return random.random() #adjust this to get the actual correlation value
all_pairs_vals=[] #list for all the source (src) and taget (trg) indexes and the corresponding correlation values
for i in range(len(src_words)): #iterate over src indexes
src_word=src_words[i] #identify the correponding src word
for j in range(len(trg_words)): #iterate over trg indexes
trg_word=trg_words[j] #identify the correponding trg word
val=match_indexes(src_word,trg_word) #get the matching value from the inverted indexes of each word (or from the data provided in the speadsheet)
all_pairs_vals.append((i,j,val)) #add the sentence indexes for scr and trg, and the corresponding val
all_pairs_vals.sort(key=lambda x:-x[-1]) #sort the list in descending order, to get the pairs with the highest correlation first
selected_alignments=[]
used_i,used_j=[],[] #exclude the used rows and column indexes
for i0,j0,val0 in all_pairs_vals:
if i0 in used_i: continue #if the current column index i0 has been used before, exclude current pair-value
if j0 in used_j: continue #same if the current row was used before
selected_alignments.append((i0,j0)) #otherwise, add the current pair to the final alignment point selection
used_i.append(i0) #and include it in the used row and column indexes so that it will not be used again
used_j.append(j0)
for a in all_pairs_vals: #list all pairs and indicate which ones were selected
i0,j0,val0=a
if (i0,j0) in selected_alignments: print(a, "<<<<")
else: print(a)
Это проблематично, потому что он не поддерживает выравнивание «многие ко многим» или даже «один ко многим» и может легко ошибиться в начале, выбрав неправильную пару с наивысшей корреляцией, исключив ее строку и столбец из будущего выбора. Хороший алгоритм будет учитывать, что определенная пара имеет самую высокую корреляцию в соответствующей строке/столбце, но также будет учитывать близость к другим парам с высокой корреляцией.
Вот некоторые данные, которые вы можете попробовать, если хотите, они находятся в таблицах Google: https://docs.google.com/spreadsheets/d/1-eO47RH6SLwtYxnYygow1mvbqwMWVqSoAhW64aZrubo/edit?usp=sharing