Нечёткий поиск. Bitap алгоритм, модификация от Wu-Manber

Подробное описание  алгоритма здесь. Для эмуляции битовых операций использовалась эта публикация. Код можно выполнять и на сервере и на клиенте. Попутно вычисляет расстояние Левенштейна.

Использовалась эмуляция, а не сами битовые операции, так как эмуляция может работать на гораздо бОльших текстах и гораздо быстрее.

функция ПобитовоеУмножение(Число1,Число2,ФорматнаяСтрока)
возврат СтрЗаменить(СтрЗаменить(Формат(Число(Число1) + Число(Число2), ФорматнаяСтрока), "1", "0"), "2", "1");
КонецФункции

функция ПобитовоеСложение(Число1,Число2,ФорматнаяСтрока)
возврат СтрЗаменить(Формат(Число(Число1) + Число(Число2), ФорматнаяСтрока), "2", "1");
КонецФункции

функция СдвигВПраво(Число1,n)
возврат "1" + лев(Число1,n-1);
КонецФункции

функция АлгоритмНечеткогоПоиска(Текст,СтрокаПоиска) экспорт
m = СтрДлина(Текст);
n = СтрДлина(СтрокаПоиска);
//для формирования нулевого битового вектора нужной длины
ФорматнаяСтрока = "ЧЦ="+формат(n,"ЧГ=0")+"; ЧН=; ЧВН=; ЧГ=0";
//заполнение вспомогательных битовых векторов на каждый символ строки поиска
U = новый Соответствие;
для i = 1 по n цикл
ключ = сред(СтрокаПоиска,i,1);
БитовыйВектор = U.Получить(ключ);
если БитовыйВектор = Неопределено тогда
БитовыйВектор = формат(0,ФорматнаяСтрока);
КонецЕсли;
БитовыйВектор = лев(БитовыйВектор,i-1) + "1"+прав(БитовыйВектор,n-i);
U.Вставить(ключ,БитовыйВектор);
КонецЦикла;
МассивНоваяПопытка = новый Массив(m);
//макс расстояние Левенштейна
МаксОшибка = макс(2,цел(СтрДлина(СтрокаПоиска)/10));
Для Ошибка = 0 по МаксОшибка цикл
M1 = формат(0,ФорматнаяСтрока);
МассивПредыдущаяПопытка = новый массив;
Для каждого стр из МассивНоваяПопытка цикл
МассивПредыдущаяПопытка.Добавить(стр);
КонецЦикла;
для j = 1 по m цикл
БитовыйВектор = U.Получить(сред(Текст,j,1));
Если БитовыйВектор = Неопределено тогда
БитовыйВектор = формат(0,ФорматнаяСтрока);
КонецЕсли;
УмножениеСВектором = ПобитовоеУмножение(СдвигВПраво(M1,n),БитовыйВектор,ФорматнаяСтрока);
Если Ошибка = 0 тогда
ПредыдущаяПопыткаj_1 = формат(0,ФорматнаяСтрока);
иначеЕсли j = 1 тогда
ПредыдущаяПопыткаj_1 = формат(0,ФорматнаяСтрока);
иначе
ПредыдущаяПопыткаj_1 = МассивПредыдущаяПопытка[j-2];
КонецЕсли;

Если Ошибка = 0 тогда
ПредыдущаяПопыткаj = формат(0,ФорматнаяСтрока);
иначе
ПредыдущаяПопыткаj = МассивПредыдущаяПопытка[j-1];
КонецЕсли;

вставкаM1 = ПобитовоеСложение(УмножениеСВектором,ПредыдущаяПопыткаj_1,ФорматнаяСтрока);
УдалениеM1 = ПобитовоеСложение(УмножениеСВектором,СдвигВПраво(ПредыдущаяПопыткаj,n),ФорматнаяСтрока);
ЗаменаM1 = ПобитовоеСложение(УмножениеСВектором,СдвигВПраво(ПредыдущаяПопыткаj_1,n),ФорматнаяСтрока);
//результат = вставкаM1 или УдалениеM1 или ЗаменаM1
M1 = ПобитовоеСложение(вставкаM1,УдалениеM1,ФорматнаяСтрока);
M1 = ПобитовоеСложение(M1,ЗаменаM1,ФорматнаяСтрока);
МассивНоваяПопытка[j-1] = M1;
Если прав(M1,1)="1" тогда
//найденная позиция - последний символ подстроки в тесте
//так как длина подстроки и строки поиска может быть разной,
//то ищем где первые ошибка+1 бит = 1, остальные 0
СтрокаДляСравнения = формат(0,"ЧЦ="+формат(Ошибка+1,"ЧГ=0")+"; ЧН=; ЧВН=; ЧГ=0") ;
СтрокаДляСравнения = СтрЗаменить(СтрокаДляСравнения,"0","1");
СтрокаДляСравнения = СтрокаДляСравнения + формат(0,"ЧЦ="+формат(n-Ошибка-1,"ЧГ=0")+"; ЧН=; ЧВН=; ЧГ=0");
Для Инт = -(j-1) по 0 цикл
Если МассивНоваяПопытка[-Инт] = СтрокаДляСравнения тогда
Прервать;
КонецЕсли;
КонецЦикла;
возврат(новый Структура("Слово,позиция,ошибок",Сред(Текст,-Инт+1,j+Инт),-Инт+1,Ошибка));
КонецЕсли;
КонецЦикла;
КонецЦикла;
возврат(новый Структура("Слово,позиция,ошибок","",0,0));
КонецФункции