Есть база (кому интересно 115ФЗ) примерно 6к+ записей
Там есть ФИО, ДР, паспорт, адрес

Есть анкеты клиентов где тоже есть эти данные ФИО, ДР, паспорт, город, телефон и т.д.
Анкет клиентов на данный момент 4к+, и каждый месяц +200.

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

Требуется сделать проверку всех наших анкет с нечетким поиском в перечне.
Типа есть у нас Иванов Иван Иванович, а в перечне есть Иванов Иван Петрович - тогда этот наш Иванович И.И. должен попасть в список на проверку оператором.

Алгоритм должен работать очень шустро.
Максимум на проверку 10к среди 10к 2-5 минут.

+(171) правда там на Delphi7. Кодировка ANSI.

(174) мне как то пофиг я только питонов не люблю, жуются плохо

а дельфи тем более 7, еще с турбо паскаля на ура идет

Скинул свое решение для 7.7

(175) да я про кодировку. в новых delphi string юникодный. если нет 7, то придется переделывать.

(177) это фигня, в лазарусе прекрасно компилится, только преобразование кодировки добавил чтобы нормально выводил вместо ?????

но чуял что где то наколка ))

подставил свой список за период из 1600 фио, за 00:00:51:015 отработало

но это решение все таки половинчатое, оно предполагает что хоть что то Ф, И или О обязательно правильно ввели и оно правильно в перечне тоже

1    28,57    АБРАМОВА ЮЛИЯ ВАСИЛЬЕВНА    ГАНЖА ЮЛИЯ ВАСИЛЬЕВНА
!нет в списке АБРАМОВСКАЯ ОЛЬГА ИГОРЕВНА
!нет в списке АБУГОВА МАРИЯ ИЗБУДИНОВНА
!нет в списке АВАЛИАНИ НАТАЛЬЯ ЮРЬЕВНА
1    23,08    АВДЕЕВ СЕРГЕЙ ВЛАДИМЕРОВИЧ    ЖАРКОВ СЕРГЕЙ ВЛАДИМИРОВИЧ
2    23,08    АВДЕЕВ СЕРГЕЙ ВЛАДИМЕРОВИЧ    ЗАХАРОВ СЕРГЕЙ ВЛАДИМИРОВИЧ
3    28,00    АВДЕЕВ СЕРГЕЙ ВЛАДИМЕРОВИЧ    ЗЫБИН СЕРГЕЙ ВЛАДИМИРОВИЧ
4    28,00    АВДЕЕВ СЕРГЕЙ ВЛАДИМЕРОВИЧ    ЗЫБИН СЕРГЕЙ ВЛАДИМИРОВИЧ
5    23,08    АВДЕЕВ СЕРГЕЙ ВЛАДИМЕРОВИЧ    КАТУНЦЕВ СЕРГЕЙ ВЛАДИМИРОВИЧ
6    23,08    АВДЕЕВ СЕРГЕЙ ВЛАДИМЕРОВИЧ    ЛЕОНОВ СЕРГЕЙ ВЛАДИМИРОВИЧ

(178)+ 1    28,57    АБРАМОВА ЮЛИЯ ВАСИЛЬЕВНА    ГАНЖА ЮЛИЯ ВАСИЛЬЕВНА  - чисто технически нужно смотреть паспорт на вопрос штампов прежних Ф и(или) еще что ))

(178) "что хоть что то Ф, И или О обязательно правильно ввели"
да нет. ему вообще по барабану. всё зависит от функции сравнения. какой процент совпадения тебе нужен.

const
  LevenProcConst: Extended = 30; //процент несовпадений в нечетком сравнении

вот LevenProcConst и крути

(180) тогда слишком долго считает...

Я сделал. Скорость приметно 5 сек на 200 тыс записей. Если допускать, что хотя бы одно поле должно совпадать то скорость вырастет раз в 10. Если допускать, что первая буква в Фамилии введена правильно, то скорость вырастет в два раза. Скорость пропорционально объему базы. Для 6 тыс записей скорость поиска << 1 сек  
Нечёткое сравнение с возможностью вместо любого символа иметь что угодно. Если ищем "Иванов" тогда делаем фильтр
( Рег.Наименование LIKE "%иванов%") ИЛИ( Рег.Наименование LIKE "%ванов%") ИЛИ( Рег.Наименование LIKE "%и%анов%") ИЛИ( Рег.Наименование LIKE "%ив%нов%") ИЛИ( Рег.Наименование LIKE "%ива%ов%") ИЛИ( Рег.Наименование LIKE "%иван%в%") ИЛИ( Рег.Наименование LIKE "%ивано%") ИЛИ( Рег.Наименование LIKE "%иванов%")

Можно список поиска втаскивать в таблицу значений, к помещать ее во временную таблицу и к таблице уже делать запрос. А можно в регистре сведений хранить информацию

(182) люблю лисапедистов ))
после них мопед, супербайком кажется клиентам

(182) еще чуть чуть и дойдем до понимания метода N-грамм

Однако все это работает и будет работать не на копеечных 6 тыс записей, а на 6 млн :) Хотя хозяин барин.

Ты можешь бороться с
АВДЕЕВ СЕРГЕЙ ВЛАДИМЕРОВИЧ  =  ЗЫБИН СЕРГЕЙ ВЛАДИМИРОВИЧ

(181) ну так всех, кого надо нашло. или нет?
а что на Lazarus медленно, так попробуй без отладчика запустить или это перекодировки в UTF8 сжирают время. На дельфях твой список из 5000 у меня за 4 секунды пролетает.

(182) ну а теперь проделай это с остальными 1999999 людьми и скажи сколько это времени заняло

Надо нейросеть учить

Мой метод даст в лучшем случае
авднеев сероей влажимирович  = авдеев сергей владимирович

(190) перестановки двух символов?
это после пропусков и лишних букв такая же частая ошибка

Перестановку тоже даст

(191)+ вадеев сегрей владиимрович

Наверно

(192) и чем он лучше метода n-грамм ?

(189) думал, а какую порекомендуете?

я только с однослойными персептронами развлекался

Перестановку берешь вместо "%" "_ _"

Конечно если
АВДЕЕВ СЕРГЕЙ ВЛАДИМЕРОВИЧ  = Иванов Иван Иванович без нейросети не обойтись :)

К слову % корректно съест
вадеев сегрей владиимрович = авдеев сергей владимирович

(180) сорри, сча соображать уже не могу, age++

так что позже отпишусь что меня смущает в этом методе
принцип то понятен, ограничение полной проверки разными способами

авдеев сергей владимирович = ХХХев сеХХХей влХХХ = Авдеев С. В.
  Надо только чтобы Фамилия, Имя, Очество были в отдельных колонках. И самое интересное, что это все работает очень быстро.
  Если немного подумать, то можно список из 1 млн строк нечетко сравнить со списком из другого 1 млн строк

(200) я знаю почему на лазарусе тормозит. там по умолчанию не работает двоичный поиск. замени функцию на это и всё залетает
procedure LoadStringList(T: TStrings; filename: string);
var
  i: integer;
begin
  T.LoadFromFile(filename);
  for i := 0 to T.Count - 1 do
    T[i] := FormatFio(T[i]);
  TStringList(T).Sorted := True;
end;

(201) уже нашел простой в использовании способ, причем он универсальный без. разницы какого вида строки (сколько там пробелов и т.д.)
линейно зависит от длин строк

для 1 млн х 1 млн примерно 10 млн миллисекунд потребуется

а про то что пишешь, это нечто вроде построения множества символьных масок/шаблонов и затем поиск строк им удовлетворяющим

две проблемы:
1. время на постройку/формирование этих масок/шаблонов
2. при увеличении длины строк линейно увеличивается время  построения масок это мелочи, но квадратно увеличивается время на проверку (так как количество разных вариантов масок/шаблонов вырастает)

+(202) ну и в StartProcess добавь в конце

  FioList.Free;
  MasterFioList.Free;

(204)

"R := (R / L) * 100;
result := R <= LevenProcConst;"

когда const
  LevenProcConst: Extended = 30; //процент несовпадений в нечетком сравнении

точно нет ошибки?

(205) ну это не совсем процент. Я эту фигню к длине строки пытаюсь прилепить. Функция же выдает количество вставок, замен  и удалений. На слове из 3 букв это одно, а на слове из 30 букв это другое. Можешь заменить на любую функцию. Я просто в инете нашел, вроде работает.

(206) ты не понял ))

там выше если разница 0 то ложь,
а тут если разница меньше или равна 30 то истина ))

(207) ЕСЛИ 0 ТО СЛОВА ОДИНАКОВЫЕ. НАМ НЕ НУЖНЫ ОДИНАКОВЫЕ. МЫ ОДИНАКОВЫЕ ПРОПУСКАЕМ.

Блин большие буквы потому что на телефоне нитуда тыкнул

(209) это ладно, просто для меня логика программы совсем непонятная

я не так думаю, совсем не так, и не так код пишу

т.е. никаких возвратов/выходов досрочно из процедуры/функции, всегда до конца доходим с помощью условий и в конце возвращаем результат установленный по пути

если выход досрочно то это try-catch сработал

и зачем
"function LevenProc(s, t: string; var R: Extended): boolean;"

когда можно
function LevenProc(s, t: string): Extended;
?

но это мелкие придирки

(210) да пиши как хочешь. Главное чтобы работало.

(163) Не сношайте мозг.
если цена одной ошибки настолько высок - обеспечивайте потребный ресурс для снижения вероятности ошибки до приемлемого для вас уровня.

(212) ничего... и до складов как нибудь свой егаис, платон или 115фз доберется...

(213) "..только в эру эту прекрасную нам не жить ни тебе уже и не мне...." ;-) - и слава богу! ;-)

(214) ви таки так плохо думаете о наших законодателях?

А насчет цен ошибки, проблема что $ то откуда взять на этот дополнительный прогрессивный (причем от количество продаж а не от суммы) налог?

Вот сча разбираемся Алинину как Аликину забили в базу, случайно выплыло она от СМС решила отказаться.

А до этого было что у нас у человека в базе фамилия почему то нету в карточке (и как смогли догадаться занести у меня там запрет пустых), а по его имени и отчеству в перечне числится "нетоварищ"

Как успехи в нечетком сравнении ФИО.
Я придумал небольшое дополнение к велосипеду, которое проводит нечеткое сравнение по ТРЕМ символам. Т.е. перестановка двух символов местами, опечатка в одном символе, залипание клавиш, изменение двух символов в трех соседних и как бонус - двойные фамилии.
  Иванов Иван Иванович
  Иавнов Иван Иванович
  Ивааанов Иоан Иванонанович
  Петров-Иванов Иван Иоанович
  Оказывается один и тот же человек

Этот алгоритм работает с параноидальной подозрительностью. Он должен быть востребован в рамках современной действительности.  На твоей базе 6000 фамилий проверка 200 фамилий будет занимать меньше 1 сек

(218) патентуй :)

(219)+ особенно если замены "а" на "a" или "о" на "o" нормально отрабатывает
причем без предварительной замены иначе как имена на английской раскладке без преобразования...

Было лень все читать. Как я делал в свое время и какие основные выводы почерпнул.
1) 1С здесь вообще не при делах(скорость важна, как форма отображения пожалуйста)
2) Реляционные СУБД тоже не очень подходят - но в моем вариантов особых не было, поэтому применялись следующие варианты комбинаторики.  
Сразу скажу что ошибка в два и более символа это уже на основании словарно-справочного сопоставления.

Основная концепция построена на предрасчете(типа как ОЛАП кубы рассчитываются) Берется слово оригинал - к нему рассчитывается большое количество комбинаций слов с одной ошибкой. Как это делается - Путем простой замены каждого символа на любой проивзольный. Также аналогично делается для +1 и -1 символ близлежащий. Таким образом можно сопоставлять. Далее можно накладывать ограничения типа "нельзя столько и таких согласных подряд". Далее можно включать словарное сопоставление. Получается соотношение один ко многим. Служебная база очень растет, Но возможно сопоставление в онлайне. Если же онлайн не важен то тут другие алгоритмы, реляционные СУБД не самый лучший выбор.

Да и еще эти задачи хорошо параллелятся и поэтому скорость очень зависит от оборудования(при хороших алгоритмах).

Обратите внимание как яндекс подсказки выдает. Можете подумать об ограничениях.

(223) яндекс выдает подсказки на методе n-грамм + захардкоженный словарик

примеры:
водка = вотка - ищется
вобла = вопла - не ищется

(221) а проблема в принципе решена, при небольших объемах (до нескольких тысяч строк, причем строки до 150 символов)
даже просто расстояние Левенштайна нормально работает
при реализации на общих языках и засовывании все в память

если нужно "еще быстрее" то специальные методы с построением битовых хешей строк (коротких к примеру 32 бита) и сравнении уже только их

(217)  вот вы все продолжаете велосипед изобретать
Эти ваши перестановки по трем символам стрмач автоматом понимает что эти пять фамилий очень близки по похожести
Он их в пуле похожих автоматом поверху выдаст

С недели две назад клиент нарисовался
Я ему дохренища лет назад рм писал для магазина радиодеталей для заказов по прайсам поставщиков - до сих пор работает клиент счастлив
А у него сиуевина посложнее чем с фамилиями была - у него все буквенно цифровое и все короткое и надо было похожее искать
И даже в таких сложных условиях стрматч спавлялся очень хорошо
Без оператора нифига все равно не обойдетесь
Всегда какаяниь фигня вылезет типа щекатурка и штукатурка

(220) Ему до лампочки русский на английский работает без предварительный замены. Алгоритм красивый и умнее всех нас вместе взятых. Обрабатывает пропуски 1-2 букв.
  А мой алгоритм ищет
водка = вотка
вобла = вопла
воводка
вовыводка и так далее и тому подобное

(227) да тут уже предлагали нейронные сети...

(228) № патента? ну или хотя бы авторского свидетельства

Свой алгоритм я тестировал на прайсах по запчастям. 250 тыс строк за 5 сек. Это уже с выводом отфильтрованных строк регистра сведений

(231) а можно хоть что то для подтверждения? хотя бы видео?

Идея - смотри (182). Это нулевое приближение. За 1 мин этот алгоритм меняется до уровня (228)

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

щекатурка и штукатурка по моему при поиске по трем символам мой алгоритм посчитает разными вернее
щекатурка = штукатурка
штукатурка <> щекатурка
  В этом что-то есть, для дополнительной фильтрации

(233) хаха ))

"По рзелульаттам илссеовадний одонго анлигйсокго унвиертисета, не иеемт занчнеия, в кокам пряокде рсапожолены бкувы в солве. Галвоне, чотбы преавя и пслоендяя бквуы блыи на мсете. Осатьлыне бкувы мгоут селдовтаь в плоонм бсепордяке, все-рвано ткест чтаитсея без побрелм. Пичрионй эгото ялвятеся то, что мы не чиатем кдаужЮ бкуву по отдльенотси, а все солво цликеом. "

(236) У тебя в каждом слове по две ошибки через правильный символ. Такого он конечно не съест. А вот
  Иванов Иван Иванович
  Иавнов Иван Иванович
  Ивааанов Иоан Иванонанович
  Петров-Иванов Иван Иоанович
съест

(237) проблема слишком много будет ложных срабатываний
можешь сам убедиться

Иванов, Пиванов, Упиванов, Выпиванов, Черезногузадерищенкованов....

Естественно по этому и надо несколько полей

Фамилия, имя, отчество ну а потом оператор

Согласись, что Иванов, Пиванов - это одно и тоже. Ошибка в одной букве

(241) для поиска "Пиванков" нет

Иванов = Пиванов
Иванов <> Пиванков
Иванов = Иванков

Конечно там есть побочные эффекты типа
Иванов = Иванкян - это правильно, если ты допускаешь ошибку в трех буквах

(243) по сути то что предлагается это обычный "Алгоритм расширения выборки"
из http://habrahabr.ru/post/114997/

только без составления словаря, вместо этого составляем "шаблоны поиска"

Да только он реализован средствами базы по индексированному полю. Поэтому очень быстрый. Более того Алгоритм расширения выборки они не смогут реализовать по трем символам. А у на он реализован

(246) и все равно процент достоверности в сравнении со скоростью поиска никакой ))
т.е. если посчитать "качество" алгоритма то будет хуже других стандартных

вот для сопоставления номенклатуры скажем может и катит (по артикулам/кодам зарытым внутри длинной строки в вперемешку с хламом)

Если ты ищешь во трем полям, то все получается великолепно. Ну и конечно если ошибок не очень много

Качество поиска великолепное.
Есть две большие разницы ошибка в одной букве, ошибка в двух буквах и перестановка, ошибка в трех буквах и перестановка, английский/русский алфавит

Что просишь, то и получаешь. Если делать поиск по словарю как (245) Словарь 100 тыс слов,
То "крокодил" - отработает замену трех символов за время << 1 сек.

(249) очень сложно "уровень похожести" регулировать для выборки
точнее даже никак

Ты делаешь предварительную выборку по мягкой схеме ТРИ символа, а потом на результате делай уровень похожести

(252) можно конечно, но зачем?
когда сразу можно искать с заданным уровнем похожести?
причем этот поиск даже быстрее будет

вот предварительная подготовка (разовая) построение хешей и запись их в базу (получение их нее) да не очень быстро

(236)  

"По рзелульаттам илссеовадний одонго анлигйсокго унвиертисета, не иеемт занчнеия, в кокам пряокде рсапожолены бкувы в солве. Галвоне, чотбы преавя и пслоендяя бквуы блыи на мсете. Осатьлыне бкувы мгоут селдовтаь в плоонм бсепордяке, все-рвано ткест чтаитсея без побрелм. Пичрионй эгото ялвятеся то, что мы не чиатем кдаужЮ бкуву по отдльенотси, а все солво цликеом. "
  Имея словарь на 100 тыс символов. При условии, что первая и последняя буква правильная, что внутри буквы могут быть переставлены в произвольном порядке, а несколько букв добавлены, алгоритм (182) прочитает данный текст без ошибок на уровне 99%. Чуть хуже, чем человек. Человек привлекает для фильтрации контекст.

Если еще хотя бы совпадал еще и слог. А вот если еще прикрутить дополнительный анализ, то может прочитать все.

Я вас умоляю - 200 анкет в месяц явно не стоят сложных алгоритмов. ФИО в 200 записей можно и глазами просмотреть.

(256) в день...
"все что они делают руками - все плохо..."

(256) да там алгоритм примитивный, вся программа в 20 строчек да функция расстояния Левенштейна, которая тупо копипастится из интернета.

Здравствуй, бложек.
С утра встал в прекрасном настроении и сделал вариант с хешированием по сигнатуре. Отрабатывает за 1,5 секунды.
Прежний вариант (154) отрабатывал за 4,5 секунды. Прогресс!

(259) ага ))

(259) длина битового хеша какая?

(261) тупо со статьи на хабре стырил. 13

(261) да он у меня и не битовый. просто строка с нулями и единицами

(263) ыыыы, ты переведи на битовый )) и дальше XOR'ами

слегка удивишься ))

(264) писал уже вроде, на тестовых 1 запись среди 10к за 1 мс при подборе похожих
это как бы тысячная доля секунды

(264) да это не тот хеш
ты про simhash наверное говоришь

(266) а когда хеши сравниваются это уже пофиг
от видов хешей зависит только качество поиска и скорость подготовки базы
а ищем то потом все равно одинаково по числу различий в битах

(267) да у меня после этого хеширования всего штук 300 хешей получается на твою базу из 5000 фамилий. там даже смысла нету в битах это хранить. ну сэкономлю 100 миллисекунд. фигня.
Попробую simhash теперь запилить.

+(268) вот для simhash важно хранить в числе и быстро разницу в битах считать, потому что там на каждую фамилию будет свой хеш, если я правильно понял эту хрень.

+(269) ну не на каждую фамилию, а на группу похожих фамилий.

Гы. Получается, в нашем случае, когда похожих ФИО мало, simhash вообще нафиг не нужен. Тратить время на его создание глупо и смешно, если он действительно долго создается.

(271) нет не долго, долго это относительно поиска по нему

(269) (270) не совсем, для симхеш можно просто нужную длину выбирать и этим регулировать как хочется размеры похожести

(272) ну у тебя сколько по времени хеши генерятся?