Каталог решений - Нечёткий поиск. 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));
КонецФункции