Как лучше всего сопоставить две строки?

Question

Знаете ли вы какие-нибудь хорошие алгоритмы, которые сопоставляют две строки, а затем возвращают процент совпадения этих двух строк?

А есть ли такие, которые тоже работают с базами данных?

Answer 1

А Расстояние Левенштейна это такая мера.По сути, он сообщает вам, сколько символов необходимо отредактировать, удалить или добавить, чтобы перейти из первой строки во вторую.Я не уверен, поддерживают ли это некоторые системы баз данных.

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

Answer 2

Это зависит от ваших критериев сходства.Другие люди уже рекомендовали вам расстояние Левенштейна (редактировать расстояние - то же самое).Обычно это довольно хорошо и определенно более независимо от языка, чем что-то вроде soundex.Однако имейте в виду, что разница Левенштейна не очень хорошо справляется с транспозицией.Таким образом:

Levenstein("copy", "cpoy") == 2

Если вы пытаетесь справиться с человеческим вкладом, транспозиции довольно распространены.Является ли это проблемой или нет, зависит от ваших показателей сходства.

Прошло много времени, но я считаю, что Postgresql уже levenstein() либо встроенный, либо доступный в качестве contrib Модуль С.

Answer 3

Я думаю, проблема, которую вы ищете, называется Изменить расстояние.В целом вычисления обходятся дорого, но если вы ищете строки на небольшом расстоянии редактирования от других строк, это не так уж и плохо.Дополнительную информацию можно найти в статье в Википедии.

Answer 4

Как лучше всего сопоставить две строки?Предложите им пойти выпить кофе, а если они поладят, то поужинать и сходить в кино.Или, может быть, они могли бы заняться партнерским программированием?На самом деле это зависит от струн.Даже кофе часто может быть непростым.

Answer 5

Поможет ли это?Я просто столкнулся с этим. Сравнение двух строк с получением числовой дельты