Сначала позвольте мне объяснить, что я подразумеваю под «выравниванием».
Допустим, мы имеем строки: например, AGBCDEF ABCDIEFK
Их «выравнивание» будет:
A - G - B - C - D - - E - F - A - - B - C - D - I - E - F - K ----------------------------------- A - ? - B - C - D - ? - E - F - ?
Другой (довольно упрощенный) пример (поскольку я считаю, что мой вопрос, вероятно, имеет отношение к НЛП):
I give Mary a kiss I give Ann a book ---------------------- I give X a Y
Как бы вы это сделали? Любые идеи (или даже ссылки) относительно алгоритма?
Я, вероятно, собираюсь написать это в Objective-C (или PHP), но любой код будет приветствоваться.
Я думаю, что вы ищете самую длинную общую подпоследовательность.
Я думаю, что вы ищете что-то вроде минимального расстояния редактирования от обработки естественного языка. Посмотрите демо-версию алгоритма расстояния Левенштейна