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

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

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

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

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

(0) + дополнение, все усложняется что не только по одному полю ФИО искать и сверять но и по другим (паспорт, адрес)

запрос ПОДОБНО

условия по другим полям
ИЛИ
ИЛИ
ИЛИ
и тд

(2) что и чему подобно?

Иванов подобно Иавнов?

(4)+ и это не решает проблему "запросов в цикле"...

ПОДОБНо единственный метод во всей 1С который может искать какие то вхождения.

в запросах.

Какие еще запросы в цикле.. ты чо несешь.

По поводу скорости: 4к вообще ниочем.
Даже для 100 000 никаких проблем нет.

(6) т.е. про http://1clancer.ru/article/polnotekstovoj_poisk_i_nechetkij_poisk_720 не слышали?

(8) у нас 10 тысяч записей, каждую из наших нужно сверить с базой тоже 10 тысяч
классический запрос в цикле, и пофиг что эти циклы сам sql сервер будет делать
время выполнения такого запроса представляем?

http://v8.1c.ru/overview/Term_000000275.htm

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

(9) может хорош путать https://helpf.pro/faq/view/852.html
обычный "like" и "нечеткий поиск"

когда нужно искать если есть ошибки при вводе и у нас и в базе

(10) нифига не понял какие еще циклы.
Поисковую строку делаешь. Пишешь запрос. Метод ПОДОБНО.
Все.

(12) то решение не устраивает по скорости и кроме 1С 8.X есть еще и 1С 7.7

(14) eqlb ghfnbdysq

(16)+ сорри
не подходит "подобно" потому что оно ищет вхождения

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

про расстояние Левенштайна слышали? А хеширование по сигнатуре?
http://habrahabr.ru/post/114997/

я не знаю что ты хочешь но в 1С всего два варианта и больше никаких.

Либо ПОДОБНО либо полнтекстовый поиск. У него минимум методов в СП

и другого не дано.

можешь хоть головой об стену бится. искать и думать что есть еще варианты - но их нет.

(18)(19) спасибо, только где в (0) хоть слово про 1С?

для восьмерки без вариантов.
Для семерки походу только с ВК. и то если такие есть.

(20) иногда лучше не показывать свою некомпетентность в вопросе не?

(22) ВК есть, причем несколько
проблему скорости они не решают

(21) тут сайт по 1С.
Если речь не про 1С - какого уя ты мосх тогда делаешь. надо было и пасть что не 1С а указывать конкретно СУБД, ПО и прочее.
В надежде найти что тут найдутся спецы по другим СУБД.

(25) Ну реально ну что ты прицепился?
На раздел то глянь

Ну не решают. Чо те сказать. Ничего.
Я ушел. тема скучная - разбирайтесь со своими таркаканами как хотите. Шансов что тут найдутся телепаты который вам забесплатно напишут суперскоростной поиск по хз каким требованиям поиска в неизвестном ПО - стремятся к нулю.

(27) как и сам напишу, поднял тему потому что она многих сча касается

и скажу огромное спасибо за куда копать и что почитать

(26)
"по скорости и кроме 1С 8.X есть еще и 1С 7.7"

"хоть слово про 1С?"

без комментариев.

(28)+ пока наиболее перспективно это:

1. Сначала "Хеширование по сигнатуре" - т.е. все записи делим на группы
Это дает сокращение для последующей проверки

2. Далее "Расстояние Дамерау-Левенштейна"

(29) читать то может научимся?

"спасибо, только где в (0) хоть слово про 1С?"

(31) тема напрямую к 1С не относится, разве что только тем что наша база в 1С хранится, но экспортнуть не проблема

когда начали твердить про "ПОДОБНО" причем очень настойчиво сделал резонно что не только 1С 8 есть так то.

А по моему надо так:

за ошибки в базе по рукам надавать.
А за ошибки при поиске вообще на кол.

(33) Может начнем слово держать? "Я ушел. тема скучная"©

Не подскажешь чем тема то зацепила?

А по одной записи из анкет сколько штатный поиск 1с длится?

(35) не проверял но явно больше 1 секунды и это без учета ошибок

Кроме "ФИО, ДР, паспорт, адрес" другие данные, по которым поиск то и не нужен, в базе есть?

(30)
1. Хэширование поможет, имхо, если процент ошибок заметно меньше, чем корректных данных.
Смотрел в сторону регулярных выражений?

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

(38) % ошибок небольшой, но даже одна пропущенная может стоит слишком дорого в виде штрафов

а чем регулярки тут помогут?

(36) Без ошибок не получится, наверное, при нечетком поиске.
(39) Я к тому, что поиск идет по всей базе, а не только по нужному справочнику. Если в базе много "лишнего", то убрав это "лишнее", время поиска можно сократить. Вы же не будете каждый раз искать по всем анкетам? А при двух сотнях может и время будет приемлемое.

Что, несовпадения в номерах паспортов тоже могут быть с ошибками в обоих списках?
Небольшой процент ошибок, это сколько?
Т.е. в основном записи совпадают по всем полям?

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

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

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

(42) Анкеты заносят ручками с бумажных или со слов покупателя = ошибки ввода
Скажем 1 из 10-20 анкет содержит разные ошибки (смотря кто заносил)

"Т.е. в основном записи совпадают по всем полям?" - это не понял

Т.е. все решения как избавиться от это Ф уже пройдены.
Избавиться не получится, нужно решение максимально близкое к (0).

(45) Тогда я за алгоритм N-грамм для ошибочных строк. Можно и на 1С его реализовать, но сильно не уверен в производительности, да и точность у него не 100%. В полнотекстовом поиске я не уверен еще до конца, чудит он часто очень.

(46) да полнотекстовый из 1С это эрзац решение
метод N-грамм имеет одну нехорошую для данного случая особенность

"Алгоритм N-грамм находит не все возможные слова с ошибками.
Если взять, например, слово ВОТКА, и разложить его на триграммы: ВОТКА ? ВОТ ОТК ТКА — то можно заметить, что они все содержат ошибку Т.
Таким образом, слово «ВОДКА» найдено не будет, так как оно не содержит ни одной из этих триграмм, и не попадет в соответствующие им списки."

апну пока не уснул ))

Случаем сервисов в инете для подобного нечеткого сравнения и/или поиска по строкам нет еще?

используй strmatch - дает хороший результат, если к этому пристегнуть какую-нить эвристику (типа Иванов иван Иванович из Хабаровск и Иванов Иван Иванович из Орел - скорее всего не ошибка). Работает хорошо, я на нем наблатыкался. Если хочешь - могу прогнать у себя пример (даешь исходный массив и массив который надо проверить) - покажу как работает.

(48) strmatch найдет.

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

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

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

в принципе нашел подходящий метод, самое смешное что по нему на русском нет инфы совсем

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

SOUNDEX (Transact-SQL)

Функция SOUNDEX преобразует алфавитно-цифровую строку в 4-символьный код, чье значение зависит от способа звучания строки при произношении. Первый символ кода является первым символом character_expression, преобразованным в верхний регистр. Второй, третий и четвертый символы кода являются числами, которые обозначают буквы в выражении. Буквы A, E, I, O, U, H, W и Y игнорируются, если только не являются первой буквой строки. Нули добавляются в конце при необходимости производить четырехсимвольный код. Дополнительные сведения о коде SOUNDEX см. в разделе Система индексирования Soundex.
Коды SOUNDEX из разных строк можно сравнивать, чтобы узнать, насколько похоже звучат строки при произношении. Функция DIFFERENCE выполняет SOUNDEX по двум строкам и возвращает целое число, представляющее сходство кодов SOUNDEX для этих строк.
Функция SOUNDEX учитывает параметры сортировки. Строковые функции могут быть вложенными

еще - https://msdn.microsoft.com/ru-ru/library/ms187384(v=sql.120).aspx

(10) Ну давай, используй полнотекстовый поиск, коль считаете его быстрым и удобным и динамическим ;)

...Вот только 1С сама его не использует, как бы... :)

+(10) 10000 записей, это Мгновение, для прямого запроса, написанного Абы как. Если еще и оптимизируешь, то и 100 000 записей не предел :)

(17) Вам нужен осмысленный поиск того мусора что ввел оператор. Т.е. оператор вводит Бред, а ваш поиск все понимает :)

(21) Маниак прав. Какая разница, 1С не 1С. Все едино. Все сведется к команде ПОДОБНО, или LIKE.

(30) Бред... что по вашему Индекс? :)

(37) Автор не удосужился привести структуру данных, где собрался искать.
Нет описания Индексов, если они есть :)

...нет данных...

(59) маня как был сварщиком с большими понтами, так и остался...
(54) штатный soundex ориентирован на английский язык. Но и русские версии существуют. В т.ч. "русификация" обсуждалась и на хабре, правда, уж давно. Я в позапрошлой конторе пытался реализовать по тем алгоритмам, но до нормальной работы не довел....
(17) Скорее, надо не левенштайновское, а Дамерау-Левенштайна. но уже по предварительно отфильтрованному саундэксом....

(62) да Демерау-Левенштайн (30)
но сначала симхеш (53)

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

(60) а что по вашему индекс? и чем он отличается от хеша?

(63) хозяин-барин.
хотя я б основывался на саундэксе..

(65) саундекс 1137 и 2137 слишком далеко поставит для паспортов

(66) Круто. Оператору по телефону сказал Один, а он записал Два.

(67) хотя тянул палец к 1

(66) саундекс основывается на _произношении_... хотя, если в вашей части галактики "один" произносится почти как "два"....

все не осилил....

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

в итоге имеем цикл по 1000 групп с небольшим кодом внутри...

(70) к какой группе ты отнесешь "Гадя Петрович Хреново"? :-)

(69) в нашей галактике не произносится, а заносится с помощью клавиатуры...

(71) тролль, лейвел не определим, скиллов распознания не хватает...

Мосх не ипите.
Берем пример дофигища реальных примеров: звоните ли вы в банк, куда нить в интернет магазин или еще куда.

Спрашивают ФИО и последние 4 цифры телефона.
Подозреваю что поиск делают по номеру телефона, а ФИО смотрят для подтверждения.

(72) ну вот "тысяча сто тридцать семь" и "две тысячи сто тридцать семь" и вправду достаточно далеко.
Еще раз намекаю, что соундекс - не универсальное сравнение, а сравнение по произношению...
кстати, интересно - а чего наше государство в номер паспорта КЦ не ввело?

(71) пол и дата рождения (или хотя-бы год рождения) это отдельные поля обязательные для заполнения...

смотрю на тему - и вижу что нифига никто ничего так и не может ничего автору дать реального.

Болтология одна.

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

(76) так пола нигде нету ((
а в дате рождения "все лгут"

(78) иди проспись пенсионер.

(76) год рождения у него операторы запросто перепутают...
а пол... я уже тут упоминал, как в одной базе было три вида пола: "мужской","женский", и "по соглашению сторон"...

(80) мне-то зачем? я трезвый, в отличие от....

(80) не это а то того

раскроем всем сикрет что хочешь в своей "мега" из нее сделать "гига"
и штатно нечеткое быстрое сопоставление номенклатуры и прочего...

(81) дык в той базе еще разные конторы есть... типа община адвентистов города Н

(84)+ интересно какой тогда пол нужно ставить, и как его определять?
с ДР то все понятно, хотя а если перерегистрация?

(85)
"....
Но могут действовать они не прямиком:
Шасть в купе - и притвориться мужиком,-
А сама наложит тола под корсет.
Проверяй, какого пола твой сосед!"

Тут давай его пытать я:
"Опасаюсь - маху дам!
Как проверить - лезть под платье?
Так схлопочешь по мордам..."

Но инструктор - парень дока,
Деловой - попробуй срежь!
И опять пошла морока
Про коварный зарубеж.
...
"
©

(0) https://dadata.ru/suggestions/#name

(87) на (71) сдох ((

(85) Если пытаться Автоматизировать бардак, то получится только автоматизированный бардак :)

(88) Я тоже это проверил. :)))

(0) про Sphinx уже было?)

(91) было и прошло, у меня не гугл и даже не яндекс

(92) а какая разница? Он делает то, что Вам нужно. Есть еще несколько аналогичных вариантов.

(93) "нифига он не делает"

(94)+ https://ru.wikipedia.org/w/index.php?title=Служебная:Поиск&search=лицинзия&profile=default&runsuggestion=0

(95) сорри сказано что в викимапии юзается движок http://wikimapia.org/#lang=ru&lat=64.540029&lon=40.543327&z=12&m=b&search=архунгельск

(0) Если автору не обязательно 1с, предлагаю не ломать голову заумными теориями, а просто найти в инете алгоритм сравнения строк и действовать тупым перебором, загнав предварительно все данные в память. Писать, само собой, на чем нибудь быстром (Си,Delphi,C#). Думаю, за 5-10 минут компьютер таки найдет в массиве то, что нужно автору.

(94) http://habrahabr.ru/company/sphinx/blog/61807/

(97) если бы... пусть проверка 1 фио среди 6000 тысяч занимает секунду
тогда для проверки наших 4к фио нужно 4000 секунд...

добавляем записи, добавляем проверяемые поля и ?

(99) ты попробуй сначала

(98) скажи чем мне поможет тупейший метод "Генерируем для каждого слова из словаря набор триграмм, те. 3 последовательно идущих символов" ?

когда (47) ?

(100) так попробовал уже )) зараза даже в секунду не укладывается 2-3 секунды на моем i3

(102) Ну нет так нет. Хотя не верится что то. Я бы сам попробовал, но у меня нет такого большого списка.

(101)+ гы у всех поисковиков водка=вотка захардкожено ))

попробуйте вобла=вопла поискать ))

(103) так попробуй на нескольких записях и умножить просто мс

(101) бей на диграммы :-) Тогда "вотка" найдется.

Кстати, а следующая тебя от тебя будет: как прикруть GoogleNow к эске?:)

(107) э?

(52) "максимум 5 минут и нужно (проверив сразу несколько наших тысяч по нескольким тысячам их) вывести список
с кем оператор будет уже поштучно разбираться "
- при размере основного массива ~20 тысяч и входных порций несколько сотен/тысяч - проблемы не представляет, сформируется даже быстрее чем за 5 минут.

(108) тьфу не надо я уже от яндекса прикручивал

У меня у лавочника количество основного массива ~30 тысяч, одна позиция на проверку отрабатывалась (подбор и формирование списка похожих) ~1 сек (даже меньше)

(62) тот же strmatch ищет с учетом фонетического сходства

(108) Перепутал, думал тема про распознавание тоже твоя была :)

(109) хехе
тут тонкости в умножении и количествах реквизитов для проверки сравнения

т.е. у вас малый список до нескольких тысяч (не больше 3) проверятеся по большому 20 тысяч это максимум 3 000 х 20 000

а вот 10 000 х 10 000 х 3 это насколько больше?

(110) как я понимаю управление голосом "добавить заявку покупателя Рога и копыта" не взлетело?))

(63) емае, strmatch примерно это все и реализует плюс с дополнительными фенечками - нахера изобретать велосипед? попробуйте сабж, не подойдет - тогда уже пилить другое средство передвижения

(114) я думаю на ваших объемах это будет вертеться весьма приемлемо.

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

(117) зачем пять минут, когда можно 5 секунд да?

Может регулярные выражения помогут:

v8: Регулярные выражения в 1С

Поможет только правка мозга.

в 1С ничего кроме ПОДОБНО нет и нет!

Другое дело как им воспользоваться. Так как с ним можно реально составить нужные алгоритмы.

В свое время я отталкивался от следующего правила.
В два прохода.

Первое поисковое слово (или набор символов) являются основой запроса.
Те делаем запрос с подобно по первому слову! а не всем вместе.

Если есть результат - запрос выгружаем в ТЗ и уже дальше точечно перерабатываем остальные слова.

На крайняк можно сделать для гарантии второй проход.

Если по первому слову результат запроса ноль. Берем второе слово и делаем по нему запрос.

в 90 процентах случаев по первому сработает сразу если есть чего.

Далее надо посмотреть что выйдет на результате и уже точечно его обрабатывать.

Я бы предложил плясать от дат рождения, намного проще, и выполняется в один запрос, слева присоединить таблицы с видом сравнения подобно нельзя.

поверьте по датам рождения будет меньше совпадений, чем по ФИО, если всеравно потом оператору перерабатывать

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

И я бы еще завел некий универсальный справочник ошибок. В который постепенно можно было бы вводить 100 процентные ошибки допущенные юзерами и на стадии ввода процедуру проверки.
Чтобы 1С запрещала повторять ошибки. Выдавала предупреждения с подтверждением и тому подобное.

Это сильно меньшит количество ошибок в базе - а с этим надо бороться - 100 процентов.

Ну не знаю чо автору надо. Я запустил 5000 раз список из 7 ФИО. Отработало за 5 сек. Функция примитивная, но работает.

Иванов Иван Иванович
Сергеев Михаил Илларионович
Митрофанов Иван Ивановч
Бургомистров Николай Федорович
Мздоимцев Михаил Сергеевич
Сергеев Михил Илларионович
Иванов Иван Иваныч
Митрофанов Иван Иванович

Отловило
ИВАНОВ ИВАН ИВАНОВИЧ --- ИВАНОВ ИВАН ИВАНЫЧ
СЕРГЕЕВ МИХАИЛ ИЛЛАРИОНОВИЧ --- СЕРГЕЕВ МИХИЛ ИЛЛАРИОНОВИЧ
МИТРОФАНОВ ИВАН ИВАНОВЧ --- МИТРОФАНОВ ИВАН ИВАНОВИЧ

Для начала вполне прилично

Хотя нет. Ошибся я. Маловато итераций. Запустил на списке из 10000 фио и теперь жду и не дождусь :)

И чего только в наших интернетах нету...
http://names-generator.ru/

(119) может и 5 секунд - там в основном все упирается в заполнение кеша, я программил на черных запросах - подготовка кеша занимает основное время (написать на прямом или если это на снеговике - то вообще не вопрос). а собственно сравнение входящей строки с массивом - практически мгновенно.

(122) "Те делаем запрос с подобно по первому слову! а не всем вместе.

Если есть результат - запрос выгружаем в ТЗ и уже дальше точечно перерабатываем остальные слова. "

хреновый вариант.
подходит для формализованных входных данных, в которых (условно) первое слово "определяющее"

Первоночально нужно алгоритмически расписать что ты будешь и как проверять.
А после это го уже задача будет на 90% решена

Или тебе нужен морфологический поиск как у Яндекса?

Я для начала тупо сделал бы.
Сформировал строку
ФИО+"#"+ДатаРождения+"#"+Адрес+"#"+ИНН
Веса чисел поднял бы "побольше" (такая возможность есть в стрматч)

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

А выявленные проблемные позиции - уже "обрабатывал" бы по предметно-ориентированной эвристике - да и то - при необходимости - и при этом мне кажется что вариантов для такой допобработки эвристикой - будет очень мало - имеет смысл окончательную верификацию - отдать на откуп оператору (у меня была сделана дополнительная двухпроходная верификация - "младший" оператор быстро отсеивал/разрешал явные проблемы, что для него представляло трудность - это "делегировалось" на след.уровень, уровней может быть много ;-) в принципе, справлялся младший оператор почти со всем

(134) проще телефон спрашивать и скать по последним цифрам номера.
а дальше тупо в списке уже уточнять по фамилии.

(135) так нету телефонов в базе РФМ

(136) Можно еще проиндексировать по фамилиям именам и отчествам и делать проверки сначала, допустим, в записях, где есть такое имя, потом отчество, потом фамилия. Ну и потом паспорт для верности.

(137) тебе имя для какого нить казахавобьют в фамилию или наоборот и капец товей проверке по конкретным реквизитам, а вариант (134) нормально словит, что

Курам Барым Мамед Оглы и Мамед Оглы Барым Курам - это почти одно и то же, степень совпадения бедет очень высокая

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

Но лучше соблюсти условия:
1. Делать только один запрос к внешнему компоненту, передал данные - передал запрос - поучил ответ(не будет потерь при передачи данных между 1с и компонентом)
2. База не так уж и большая, если одну запись преобразовать в строку то база будет примерно 2мега, что замечательно умещаться в памяти да и больше уместиться.
3. Есть предложение работать с регулярными вырождениями.


Как вариант еще: базу проверки выгрузить в файл, запрос сохранить в файл и скормить их какой-либо программе(в том числе и самописной на любом языке).

Общая идея выгрузить из 1с и обработать внешней магией)))) средствами 1с вы не решите данную задачу с заявленными условиями.

(0) Если базуха на скуле - то скорее подергать функционал скуля . Там что то должно быть по поиску.

(138) ну Мамед Оглы решается. Сколько слов в строке, столько и индексов создать. Сделал вариант с индексами. Приятно удивился. В виртуальной XP на i5 выдало такое:
строк: 9988
фамилий: 506
имен: 186
отчеств: 211
% несовпадений:    наши:    эталон:
7,41    ВЛАДИМИРОВА АЛИНА МАТВЕЕВНА    ВЛАДИМИРОВА ФАИНА МАТВЕЕВНА
4,35    БЕСПАЛОВА ВЕРА ГЛЕБОВНА    БЕСПАЛОВА ВЕРА УЛЕБОВНА
8,33    ЕФИМОВА ФАИНА НИКОЛАЕВНА    ЕФИМОВА ЖАННА НИКОЛАЕВНА
4,35    ГУСЕВА НАИНА НИКОЛАЕВНА    ГУСЕВА ФАИНА НИКОЛАЕВНА
8,33    ЕФИМОВА ЖАННА НИКОЛАЕВНА    ЕФИМОВА ФАИНА НИКОЛАЕВНА
4,55    МУХИНА НАИНА МИХАИЛОВНА    МУХИНА НИНА МИХАИЛОВНА
4,35    ЧЕРНОВ ВАЛЕРИЙ ГЛЕБОВИЧ    ЧЕРНОВ ВАЛЕРИЙ УЛЕБОВИЧ
6,67    НИКИФОРОВА АНГЕЛИНА МАРТЫНОВНА    НИКИФОРОВА АНЖЕЛИКА МАРТЫНОВНА
10,00    ОВЧИННИКОВА ФЕВРОНИЯ ФЕДОТОВНА    ОВЧИННИКОВА ФЕВРОНИЯ ФИЛАТОВНА
4,17    БОРИСОВ ГЕРМАН СЕРГЕЕВИЧ    БОРИСОВ ГЕРМАНН СЕРГЕЕВИЧ
8,33    АРТЕМЬЕВА НИНА РОМАНОВНА    АРТЕМЬЕВА АННА РОМАНОВНА
8,33    ЛОГИНОВА МАРФА ДОНАТОВНА    ЛОГИНОВА МАРИНА ДОНАТОВНА
4,55    МУХИНА НИНА МИХАИЛОВНА    МУХИНА НАИНА МИХАИЛОВНА
4,17    ОДИНЦОВА АЛИНА ИРИНЕЕВНА    ОДИНЦОВА ГАЛИНА ИРИНЕЕВНА
3,70    ГОЛУБЕВА НАИНА ВСЕВОЛОДОВНА    ГОЛУБЕВА ФАИНА ВСЕВОЛОДОВНА
4,35    ЧЕРНОВ ВАЛЕРИЙ УЛЕБОВИЧ    ЧЕРНОВ ВАЛЕРИЙ ГЛЕБОВИЧ
7,14    СМИРНОВА АЛИНА ХРИСТОФОРОВНА    СМИРНОВА ПОЛИНА ХРИСТОФОРОВНА
8,00    АНДРЕЕВА НОННА ЯРОСЛАВОВНА    АНДРЕЕВА НИНА ЯРОСЛАВОВНА
7,14    СМИРНОВА ПОЛИНА ХРИСТОФОРОВНА    СМИРНОВА АЛИНА ХРИСТОФОРОВНА
3,70    ГОЛУБЕВА ФАИНА ВСЕВОЛОДОВНА    ГОЛУБЕВА НАИНА ВСЕВОЛОДОВНА
10,00    ОВЧИННИКОВА ФЕВРОНИЯ ФИЛАТОВНА    ОВЧИННИКОВА ФЕВРОНИЯ ФЕДОТОВНА
4,17    ОДИНЦОВА ГАЛИНА ИРИНЕЕВНА    ОДИНЦОВА АЛИНА ИРИНЕЕВНА
8,00    АНДРЕЕВА НИНА ЯРОСЛАВОВНА    АНДРЕЕВА НОННА ЯРОСЛАВОВНА
7,41    ВЛАДИМИРОВА ФАИНА МАТВЕЕВНА    ВЛАДИМИРОВА АЛИНА МАТВЕЕВНА
4,17    БОРИСОВ ГЕРМАНН СЕРГЕЕВИЧ    БОРИСОВ ГЕРМАН СЕРГЕЕВИЧ
4,35    ГУСЕВА ФАИНА НИКОЛАЕВНА    ГУСЕВА НАИНА НИКОЛАЕВНА
8,33    ЛОГИНОВА МАРИНА ДОНАТОВНА    ЛОГИНОВА МАРФА ДОНАТОВНА
10,00    МЯСНИКОВА ФЕВРОНИЯ ЛАВРЕНТЬЕВНА    МЯСНИКОВА ЕВДОКИЯ ЛАВРЕНТЬЕВНА
6,67    НИКИФОРОВА АНЖЕЛИКА МАРТЫНОВНА    НИКИФОРОВА АНГЕЛИНА МАРТЫНОВНА
4,35    БЕСПАЛОВА ВЕРА УЛЕБОВНА    БЕСПАЛОВА ВЕРА ГЛЕБОВНА
4,17    БОГИСОВ ЕВГЕНИЙ ОЛЕГОВИЧ    БОРИСОВ ЕВГЕНИЙ ОЛЕГОВИЧ
3,85    ГАЛКИНА КЛАВДИЯЯ МИХАИЛОВНА    ГАЛКИНА КЛАВДИЯ МИХАИЛОВНА
3,45    ЕВСЕВ КОНСТАНТИН СЕРАПИОНОВИЧ    ЕВСЕЕВ КОНСТАНТИН СЕРАПИОНОВИЧ
8,33    АРТЕМЬЕВА АННА РОМАНОВНА    АРТЕМЬЕВА НИНА РОМАНОВНА
10,00    МЯСНИКОВА ЕВДОКИЯ ЛАВРЕНТЬЕВНА    МЯСНИКОВА ФЕВРОНИЯ ЛАВРЕНТЬЕВНА

time:00:00:01:420

это только проверка по фамилиям без прочих идентификаторов.
проблема только как проверить, что нашего человека нет в эталонном списке.
P.S Автор (или кто нибудь хороший) дай реальный список людей на проверить алгоритм. Только фио без прочих данных.

+(141)за полторы секунды отработало

естественно, такой вариант подходит если операторы не совсем дибилы и правильно занесли хотя бы имя или фамилию или отчество.

В конечном итоге алгоритм такой: индексируем эталонный список, проходим по своему списку и ищем в эталонном списке совпадения. Если человек не найден в эталонном списке, то ищем для него похожее имя по моему алгоритму. Как то так.

Продолжаю свой бложек. По алгоритму (144) отрабатывает за 190 миллисекунд. Лучше уже и не надо.

(145) все проще намного
для всех строк считается битовый хеш (симхеш) это линейная операция почти, зависит от длины строк

далее этот хеш для списка в котором ищем сохраняется
и вся проверка строки заключается в посчитать хеш (вида 100100011100001)

и найти все хеши которые отличаются как можно меньшим числом бит

для этого используем B-Tree индекс

(146) и шо быстро ищет?

(147) мгновенно

(148)+ но уточнить сразу нужно, индексация весьма долгая

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

но потом поиск "похожих" строк это секунды для сотен проверяемых, среди тысяч по которым проверям

(146) проще то как раз у меня. а у тебя правильнее :)

(149) более точные цифры по скорости по тестам (при учете все в памяти а не в БД)

приблизительно 1 мс выбрать хеши похожих строк для одной среди 10000 хешей
т.е. 10000х10000 (проверить 10к строк на похожесть среди 10к строк) это 10 секунд

понятно что реально с учетом переброски данных все будет медленнее
а если нужно для каждой из нескольких подобранных строк еще вычислить % похожести (тот же Дамерау-Левенштайн для пар проверяемая-найденные) то еще медленнее будет

но вот индекс реально долго строится ((

(151) Ну мой метод вместе с индексированием работает меньше секунды. Правда я сомневаюсь, что он правильный и у меня нет реальных данных, чтобы проверить. Скинь, базу ФИО без остальных данных, если не жалко.

(152) в почту отправил

Здравствуй бложек!
Короче, всё оказалось еще проще чем просто.
1. Приводим оба списка в порядок. (один регистр, один пробел между словами)
2. Эталонный список сортируем.
3. Проходим по нашему списку и
берем наше ФИО и ищем в эталонном списке. Если не находим, то полностью проходим по эталонному списку сравнивая оба ФИО функцией нечеткого поиска.
Чем больше ошибок тем дольше будет работать. Если предполагается, что ошибок не много, то такой алгоритм нас устраивает.

У меня 5000 строк и 60 ошибок отработало за 4 сек на i5

+(154) причем это время включает всё: от загрузки файлов с диска до выдачи результата

(154) т.е. 4 секунды на одно наше проверяемое ФИО ?

Вот есть "перечень" из 6000 имен, для того чтобы проверить по нему (на совпадения) одно наше ФИО сколько времени уходит?

А если нам не одно ФИО нужно проверять а несколько тысяч?
Сколько потребуется времени?
Тоже всего 4 секунды ;) ?

Мне кажется проблема немного надумана. Если бы надо было проверить 6 млн записей на таблице в 6 млн, то это было бы задачей.
У меня под рукой Регистр сведений с прайсами поставщиков на 200 тыс позиций. Установка фильтра по вхождению строки по трем полям срабатывает менее чем за 1 сек.
  К примеру ищешь "ван" через 1 сек ты получишь список
  Иванов Петр Сергеевич
  Сидоров Петр Полуванович ну и т.д
  При этом чем больше полей для анализа, тем быстрее работает поиск

Это я специально делал для быстрого поиска в прайс листах поставщиков.
УФ форма списка с возможностью программной установки отбора

(156) Нет, не на одно. 5000 наших фио на 5000 не наших. Всё за 4 секунды.

В свое время здесь проскакивала проблема. Есть КЛАДР несколько сот тысяч записей. Одна запись изменена. За несколько сек эта запись находится без проблем

(160) нужно сравнить в двух кладрах похожие названия городов
например Выдропужск и Выдропопск и т.д.

(159) нэ вэрю ))

в смысле ошибки то как? или точнее когда при забивании переврали 2 поля из 3-х?

а нельзя быть уверенным не в одной нашей записи что не переврали

Может он вовсе не "Иванов" как забили а вовсе даже "Ифанов" и не "Петрович" а "Патрович"

(162)+ если пропустим кого, то цена ошибки возможно сотни тысяч штрафа

У тебя могут быть ошибки сразу в трех словах. Если да, то тогда проблема, Если хотя бы одно слово верное - тогда проблем нет

(163) или человеческие жизни...

но не будем о грустном ))

(164) в том то то и дело, сча поищу пример посмешнее

(166) + Осина?  Пчельнокова? Каринэ?

причем так и занесено...

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

(168) оператор может набить что угодно и нужно кроме ФИО еще прочее учитывать

(162)
Ошибка - это когда в ФИО из нашего списка нет в эталонном списке.

например у нас есть Иваов Михуил Игнатьевич
в эталонном есть только Иванов Михаил Сергеевич

про другие данные это уже другой вопрос. ну пусть на них уйдет еще пару секунд.

(169) щас скину тебе свои изыскания. сам побалуйся

(170) Сейчас я сделаю эту задачку на списке 200 тыс за 1 сек

(172) давай

+(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) ну у тебя сколько по времени хеши генерятся?