Сравнение строк

Question

[Benderlidze]

Подсажите алгоритм по сравнению строк.
Необходимо быстро находить похожие фамилии, фамилии с ошибками и т.п. из базы.
Спасибо.

Comments

[couatl]

Какая база? Oracle имеет нечеткий поиск

[Benderlidze]

ох, забыл
mysql

Answer 1

[Макс]

www.php.net/manual/en/function.soundex.php
www.php.net/manual/en/function.similar-text.php
www.php.net/manual/en/function.levenshtein.php
www.php.net/manual/en/function.metaphone.php

Comments

[egorinsk]

Вроде эти функции работают только с английскими словами? Сомневаюсь, что они хоть сколько-нибудь пригодны автору. Минус вам.

Answer 2

[couatl]

Расстояние Хэмминга

Comments

[couatl]

Расстояние Левенштейна
Расстояние Левенштейна

В Oracle есть нечеткий поиск — пакет UTL_MATCH

[couatl]

http://forums.mysql.com/read.php?20,282935,282935#msg-282935

[couatl]

*алгоритм сходства Джаро-Винклера

Answer 3

[Павел Волынцев]

* Нечёткий поиск на клиенте и Soundex habrahabr.ru/post/125617/
* Фонетический поиск habrahabr.ru/post/28752/ и его модификация: Soundex по-русски p2k.ru/archives/57
* и ещё один htmlweb.ru/php/example/soundex.php (см середину статьи)

Comments

[Павел Волынцев]

CREATE TABLE person (
  id SERIAL PRIMARY KEY,
  name TEXT, -- извините за размерность
  name_hash TEXT -- извините за размерность
);
CREATE INDEX idx_person_name_hash ON person(name_hash);

INSERT INTO person (name, name_hash) VALUES ('Petroff', 'P361' /* <?php echo soundex('Petroff'); ?> */ );
INSERT INTO person (name, name_hash) VALUES ('Sidoroff', 'S361' /* <?php echo soundex('Sidoroff'); ?> */ );
INSERT INTO person (name, name_hash) VALUES ('Ivanoff', 'I151' /* <?php echo soundex('Ivanoff'); ?> */ );
-- примеры реализаций soundex для русского я указал выше

SELECT name FROM person WHERE name_hash = 'P361'; -- все кто по звучанию напоминает Petroff