Нечеткое сравнение строк

[Logger]

Здравствуйте.

Кто-нибудь делал функцию нечеткого сравнения строк ?

Суть проблемы : есть ряд записей в справочнике, у которых отличаются наименования перестановкой слов, пропуском знаков препинания и кавычек, пропуском некоторых слов и т.п. Хотелось бы поиметь некую строковую функцию, которая позволила бы определить что формально разные названия суть одно и то же.
Ну то есть понимала бы что строки
"ООО "Рога и копыта""
"Рога и копыта ООО"
"Рога и копыта, inc"
"Рога и копыта"
""Рога и копыта""
""Рога и копыта, ООО""

-реально одно и то же. Ну или могла бы дать какую-то меру близости двух строк друг к другу, чтобы мы могли понять что две строки это почти одно и то же или наоборот что они совсем разные и не могут соответствовать одному и тому же контрагенту.

Задача возникла при внедрении аксапты в филиале компании. Т.е. справочники контрагентов и номенклатур у нас похожи, но кодировка разная. При закачке справочников в аксапту появились дубликаты. Выверка по ИНН и артикулам не дает нужного результата, так как в справочниках предоставленных филиалом было много ошибок, неточностей и т.п. При любой спорной ситуации только человек по названию может определить являются ли 2 записи дублем или это разные сущности. Хотелось бы как-то облегчить людям труд по выверке справочников и сгруппировать записи которые с большой долей вероятности могут быть дублями одной и той же сущности.

[S.Kuskov]

Не так давно было похожее обсуждение Унифицированный справочник цветов

[mazzy]

Цитата:

Сообщение от Logger

Кто-нибудь делал функцию нечеткого сравнения строк ?

ну... здесь не совсем нечеткое сравнение.
нечеткое сравнение предполагает, что строки могут чуть-чуть отличаться в любом месте
алгоритм нечеткого сравнения безумно тяжелая штука и, скорее всего, будет работать долго.

здесь же предполагается, что есть некое ядро из одинаковых СЛОВ.
плюс-минус несколько разделителей и/или других слов.

если у вас ax2009 или ax4, то воспользуйтесь агентом данных:
1. главное меню \ основное \ настройка \ агент данных
2. добавьте вашу таблицу с названиями.
3. запустите агент данных.
4. пусть он переиндексирует все записи таблицы (заодно у вас заработает глобальный поиск )

в результате работы агента:
5. все тексты будут разбиты на слова, которые будут хранится в таблице SysSearchName
6. а в таблице SysSearchPath будут ссылки на выделенные слова и ссылки на записи.

Ваша задача - найти такие записи, у которых максимальное число общих слов.
А это уже вполне подъемный запрос (в отличие от алгоритма нечеткого сравнения строк ВСЕ-СО-ВСЕМИ).
А если вы еще выделите незначимые слова (ООО, Ltd и т.п.) и не будете учитывать их при подсчете, то будет вообще хорошо.

обратите внимание, что разбивка по словам выполняется в методе SysSearch::splitIntoWords
может быть, стоит допилить этот метод, чтобы научить его новым трюкам и разделителям.

[Wamr]

нечеткий поиск
Там простенький алгоритм, который элементарно реализуется на .Net и подключается как функция в БД.

[samolalex]

Ниже я разместил код джобика, реализующего простой алгоритм поиска подстроки в массиве данных:

static void IllegibleSearching(Args _args)
{
    str     strArr[9]; //массив данных
    str     searchStr = "ога и коп"; //поисковая строка
    Counter i, j;
    Set     indexSet = new Set(Types::Integer);//множество индексов найденных элементов
    ;

    strArr[1] = "ООО 'Рога и копыта'";
    strArr[2] = "Рога и копыта ООО";
    strArr[3] = "Тестовая строка1";
    strArr[4] = "Рога и копыта, inc";
    strArr[5] = "Тестовая строка2";
    strArr[6] = "Рога и копыта";
    strArr[7] = "Рога и копыта";
    strArr[8] = "Тестовая строка3";
    strArr[9] = "'Рога и копыта, ООО'";

    for(i=1; i<=9; i++)
    {
        if(strscan(strArr[i],searchStr,1,100))
            indexSet.add(i);
    }

    for(i=1; i<=9; i++)
    {
        if(indexSet.in(i))
            info(strArr[i]);
    }
}

[mazzy]

Я смотрю и удвиляюсь.
Интересно вы как-то перешли от группировки различных записей по похожести (все-со-всеми) к поиску подстроки (одной!) в наборе записей.

Цитата:

Сообщение от Logger

Суть проблемы : есть ряд записей в справочнике, у которых

Цитата:

Сообщение от samolalex

Ниже я разместил код джобика, реализующего простой алгоритм поиска подстроки в массиве данных:

Дык, у него длительность будет пропорциональна O(2*n^2) для всех работы по всем записям.

[S.Kuskov]

Цитата:

Сообщение от mazzy

Я смотрю и удвиляюсь

Мда... Этот вариант совсем не вариант . Хотя, если его развить, то может получится что-то вроде этого http://ms.by.ru/HTML/37.htm

Цитата:

Алгоритм сравнения строк. Функция нечёткого сравнения использует в качестве аргументов две строки и параметр сравнения - максимальную длину сравниваемых подстрок. Результатом работы функции является число, лежащее в пределах от 0 до 1. 0 соответствует полному несовпадению двух строк, а 1 - полной (в определённом ниже смысле) их идентичности. Сравнение строк происходит по следующей схеме. Пусть, например, в качестве аргументов заданы две строки "test" и "text" и некоторая максимальная длина подстрок, скажем, 4. Функция сравнения составляет все возможные комбинации подстрок с длинной вплоть до указанной и подсчитывает их совпадения в двух сравниваемых строках. Количество совпадений, разделённое на число вариантов, объявляется коэффициентом схожести строк и выдаётся в качестве результата работы функции.

Но боюсь, что работать это будет не просто долго, а очень долго.

Также если кому интересно http://ru.wikipedia.org/wiki/Расстояние_Левенштейна и другие Алгоритмы приблизительного сравнения текста

[Raven Melancholic]

Насколько помню историю вопроса, большинство алгоритмов нечеткого сравнения строк (самый известный Саундекс) разрабатывались под конкретную программу: перепись населения в США с первым применением автоматизированной обработки.
Отсюда недостаток - хорошо работаю на английских фамилиях, а для прочего нужно относится осторожно.
PS: хотя, в свое время, мы использовали тот же Саундекс для сопоставления номенклатуры в прайс-листах конкурентов и результаты были вполне удовлетворительными.