Как нормализовать расстояние Левенштейна для максимальной длины выравнивания, а не для длины строки?

Проблема: В нескольких пакетах R есть реализации расстояния Левенштейна для вычисления подобия двух строк, например. http://finzi.psych.upenn.edu/R/library/RecordLinkage/html/strcmp.html. Вычисленные расстояния можно легко нормализовать для длины строки, например. путем деления расстояния Левенштейна на длину самой длинной задействованной строки или путем деления его на среднее значение длин двух строк. Однако для некоторых приложений в лингвистике (например, диалектометрия и исследования рецептивного многоязычия) рекомендуется нормировать необработанное расстояние Левенштейна на длину самого длинного выравнивания с наименьшими затратами (Heeringa, 2004: 130-132). Это имеет тенденцию производить измерения расстояния, которые имеют больше смысла с перцептивно-лингвистической точки зрения.

Пример: Немецкая строка «tsYklUs» (Zyklus = цикл) может быть преобразована в родственный ей шведский «sYkEl» (cyckel = (би) цикл) в 7-слотовом выравнивании с двумя вставками (I) и двумя заменами (S) для общего Стоимость трансформации 4. Нормализованное расстояние Левенштейна: 4/7

(A)

t--s--Y--k--l--U--s
---s--Y--k--E--l---
===================
I-----------S--S--I = 4

Также возможно преобразовать строки в 8-слотовое выравнивание с 3 вставками (I) и 1 удалением (D), также при общей стоимости выравнивания 4.Нормализованное расстояние Левенштейна: 4/8

(B)

t--s--Y--k-----l--U--S
---s--Y--k--E--l------
======================
I-----------D-----I--I = 4

Последнее выравнивание имеет больше смысла с лингвистической точки зрения, потому что оно выравнивает [l]-фонемы друг с другом, а не с гласными [E] и [U].

Вопрос: Кто-нибудь знает какую-либо функцию R, которая позволила бы мне нормализовать расстояния Левенштейна для самого длинного выравнивания с наименьшей стоимостью, а не для самой длины строки? Спасибо за ваш вклад!

Ссылка: WJ Heeringa (2004), Измерение различий в диалектном произношении с использованием расстояния Левенштейна. Кандидатская диссертация, Гронингенский университет. http://www.let.rug.nl/~heeringa/dialectology/thesis/

Редактировать — Решение: Кажется, я нашел решение. Функция adistможет возвращать выравнивание и, по-видимому, по умолчанию использует самое длинное выравнивание с низкой стоимостью. Чтобы продолжить приведенный выше пример, вот выравнивание, связанное с sykelпо tsyklus:

> attr(adist("sykel", "tsyklus", counts = TRUE), "trafos")
     [,1]      
[1,] "IMMMDMII"

Чтобы вычислить нормированные по длине расстояния, как рекомендовано Heeringa (2004), мы можем написать скромную function:

normLev.fnc <- function(a, b) {
  drop(adist(a, b) / nchar(attr(adist(a, b, counts = TRUE), "trafos")))
}

Для приведенного выше примера это возвращает

> normLev.fnc("sykel", "tsyklus")
[1] 0.5

Эта функция также возвращает правильные нормализованные расстояния для примеров Heeringa (2004: 131):

> normLev.fnc("bine", "bEi")
[1] 0.6
> normLev.fnc("kaninçen", "konEin")
[1] 0.5555556
> normLev.fnc("kenEeri", "kenArje")
[1] 0.5

Для сравнения нескольких пар строк:

> L1 <- c("bine", "kaninçen", "kenEeri")
> L2 <- c("bEi",  "konEin", "kenArje")
> diag(normLev.fnc(L1, L2))
[1] 0.6000000 0.5555556 0.5000000