Как сделать поиск анаграмм с опечатками?

Question

[xmoonlight]

Допустим, есть слова-анаграммы:
AABB = ABAB, ABBA, BBAA

Теперь, в некоторых из них сделали опечатки:
AABB ~= ABAB, ABBB, BDAC
Проценты опечаток (относительно AABB): 0%, 25%, 50%.

По порогу ошибки, превышающей 25%, отсеиваем только последнее слово: BDAC.

Т.е., будет так.
Допустимый порог ошибки 25% (1 ошибка на 4 символа):
AABB ~= ABAB, ABBB
(это конечный результат)

Вопрос:
Как максимально быстро детектировать анаграммы, если в словах допущена одна или несколько опечаток с нужным порогом ошибки?

Длина слов - может быть любой, процент опечаток - может быть задан произвольно.

UPD: Примеры опечаток (сравнение анаграмм и количество опечаток):
AABB и AAB => 1 (недостающий символ)
AABB и AABBA => 1 (лишний "свой" символ)
AABB и AABBC => 2 (лишний "чужой" символ)

Comments

[Сергей Соколов]

Насколько опечаточно несовпадение длины?
AABB и AAB

[xmoonlight]

Сергей Соколов, опечаток:
AABB и AAB => 1
AABB и AABBA => 1
AABB и AABBC => 2

[Сергей Соколов]

Ещё момент уточнить: ведь «расстояние» между двумя словами точно симметрично (не зависит от перестановки мест)?
"AABB" – "AAB" === "AAB" — "AABB"

Недостаток буквы так же штрафуется как лишняя буква?

[xmoonlight]

Сергей Соколов, да. Именно так.
Расстояние - анаграммное именно.

[Сергей Соколов]

Почему лишний «чужой» штрафуется иначе, чем лишний «свой» ?

[xmoonlight]

Сергей Соколов, я добавил в вопрос апдейт.

UPD: Примеры опечаток (сравнение анаграмм и количество опечаток):....

[xmoonlight]

Сергей Соколов,

Почему лишний «чужой» штрафуется иначе, чем лишний «свой» ?

потому, что так нужно по задаче.

[Сергей Соколов]

xmoonlight, что пытались сделать сами? Что не получается? Где застряли?

[Сергей Соколов]

Задача плохо сформулирована. Условие разных штрафов за свою VS чужую букву – асимметрично:

AB  vs ABZ = 2
ABZ vs AB  = 1

[xmoonlight]

Сергей Соколов, нет, всё правильно: порядок здесь - крайне важен: слева - эталон, справа - тест.

Чужая лишняя буква - наказывается жёстче в 2 раза, чем не чужая или любая недостающая.

[xmoonlight]

Сергей Соколов,

что пытались сделать сами? Что не получается? Где застряли?

считашь, что я сразу пришёл за готовым ответом?

[Сергей Соколов]

xmoonlight, выше справшивал про симметричность. Тут вдруг выяснилось противоречие.
Задача сырая, даже не сформулирована.

[xmoonlight]

Сергей Соколов, Сырая формулировка - согласен!
"Противоречие - в чём?"
Я, кажется, понял твой вопрос (отвечаю): в том примере - не чужая лишняя буква была. (про это речь?)

[Сергей Соколов]

ведь «расстояние» между двумя словами точно симметрично (не зависит от перестановки мест)?
"AABB" – "AAB" === "AAB" — "AABB"

xmoonlight:

да. Именно так. Расстояние - анаграммное именно.

Противоречие с:

AB  vs ABZ = 2
ABZ vs AB  = 1

[xmoonlight]

Сергей Соколов, да. значит я ответил правильно.
Проблема: в Z (в примере - этого просто не было случая).

Answer 1

[twobomb]

https://jsfiddle.net/twobomb/eLnpcu9x/

Comments

[xmoonlight]

Спасибо!

Вот ошибочку нашёл: AABB и AABBC выводит 25.0%
А должно быть явно больше 25%.

Я примеры опечаток добавил в текст вопроса:

AABB и AABBC => 2 (лишний "чужой" символ)

[xmoonlight]

twobomb,
AABB vs ABBA => 50%.
Должно быть 0%.

PS: итого - уже 2 ошибки...

[xmoonlight]

twobomb, допилишь, может и я выберу решением, чтобы всем достался рабочий код.
Что скажешь?