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

← →
Tifon © (2007-02-09 15:44) [0]

День добрый! Подскажите пожалуйста возможно ли сделать функцию сравнения двух слов (в моем случае слов) и установить их соответствие, не смотря на то что в слове может быть допущена орфографическая ошибка или вставлено или добавлено слово? Ни как не могу предумать подходящего алгоритма, подскажите кто что знает.

← →
fd979 © (2007-02-09 15:51) [1]

Можно установить процент соответствия

← →
alles © (2007-02-09 15:51) [2]

function IsEqualStrings(s:string; s1:string): boolean;
begin
Result:= s=s1;
end;

← →
TRUNK © (2007-02-09 15:52) [3]

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

← →
unknown © (2007-02-09 15:52) [4]

>
> Tifon © (09.02.07 15:44)

Поищи в сети реализацию Soundex для русских букв.

← →
Tifon © (2007-02-09 16:06) [5]

а что такое SoundEx?

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

← →
unknown © (2007-02-09 16:16) [6]

> Tifon © (09.02.07 16:06) [5]
>
> а что такое SoundEx?

Алгоритм такой. Для аглицких букв есть в StrUtils.

← →
Tifon © (2007-02-09 16:19) [7]

а как он выражен, где его искать? или может уже есть такая функция?
Я нашел функцию AnsiSameStr, но она просто сравнивает без всяких соответствий и вообще, наверно с помощью обычного "If""а:(

← →
Сергей М. © (2007-02-09 17:05) [8]

> в слове ..вставлено или добавлено слово?

Сам-то ты понял что сказал ?)

← →
Desdechado © (2007-02-09 17:19) [9]

В кладовке Kerk выкладывал.

← →
Tifon © (2007-02-09 17:27) [10]

>Сам-то ты понял что сказал ?)
Извините, просто из-за этой проблемы эти слова все время крутятся в голове, иногда путаюсь.

>В кладовке Kerk выкладывал.

а что за кладовка и Kerk?

← →
vasIZmax © (2007-02-09 17:49) [11]

> alles © (09.02.07 15:51) [2]

а что так можно сейчас?

> Tifon © (09.02.07 17:27) [10]

кладовка на страницы "начинающим", смотри внимательно, а Kerk - это местный, не бойся)))))))

← →
Tifon © (2007-02-12 16:21) [12]

в кладовке нет функции которая мне нужна, есть похожая но она работает слабовато, я хочу придумать алгоритм посильнее.
У меня была идея, чтоб отследить можно просто удалять буквы которые не совпадают, но тогда появляется загвоздка, если например слова: машина и миошина. Программа удалит буквы от "и" до "н", можно сделать слежку, за вставленной или пропущенной буквой, но тут опять уменя беда, т.к. я не знаю как динамически это можно организовать, в своем старом алгоритме я просто сравнивал, при несовпадении, следующую и через неё букву, но тогда у меня получается прокол если вставленно более 2 букв.
Если написал что-то непонятно спрашивайте, и извиняйте просто все мозги в этой проге.8-()
может уже появились какие-то мысли на этот счет?

← →
Elen © (2007-02-12 17:04) [13]

> Tifon © (12.02.07 16:21) [12]

А ты пробовал воспользоваться Speller из MS Word? Помоему там чтот-то такое можно.

Чесно говоря, чувствую себя проным тупицой:(. А что такое Speller? Если это функция сравнения при которой только ошибка в одной букве может быть исправленна, то она мне не подходит, я хочу придумать, если возможно, то с вашей помощью, что-то динамичное, которое смогло б сравнивать слова независимо от их исправлений.

>А ты пробовал воспользоваться Speller из MS Word? Помоему там чтот-то такое можно.

Смотрел в разделе алгоритмы, там есть похожий но он как-то странно считает, в этом алгоритме при сравнении двух слов "Test и Text" получается коэффициент совпадения 40%, а реально если посчитать по количеству совпадающих символов он - 75%, и при чем что самое инетересное, процент совпадение увеличитвается при увеличении длины слова, почему такая не точность я не знаю, хотя он по-моему работает вообще странно.

Я придумал немного другую вещь, помогите плз закончить, объясняю алгоритм.
1. Берем искомое слово(Wright) и введенное(Input);
2. Запускаем цикл с постуслвоием (Repeat или While), нельзя с предусловием т.к. не знаем точной длины пробега.
3. Начинаем посимвольно сравнивать наши слова(начинаем(()
а) {Раньше я сравнивал так}
if (Wright[i] <> Input[i]) and (Wright[i + 1] = Input[i + 1]) ...{так я рассматривал частные случаи на количсетво неверных или вставленных символов}
А сейчас в цикле будет еще одна переменная, например L, которая будет нарасчиваться в том случае, если соседи после неверного символа не равны, при этом сравнение должно проходить не только {if Wright[i + L] = Input[i + L]} а еще и с учетом пропущенного или вставленного символа, т.е. maybe
{if Wright[i + L - 1] = Input[i + L](случай когда символ пропущен, но здесь опять таки необходимо вводить переменную вместо 1)} or {if Wright[i + L + 1] = Input[i + L](случай, когда вставлен символ и здесь опять же переменная вместо единицы, при чем эта переменная также должна нарасчиваться вместе с L или может сначала должна нарасчиваться только переменная сдвигания порядка, тут я еще точно не знаю)}.
Здесь я тоже еще пока что не уверен как пропускать проверку, сделать проверку на вставленный и пропущенный символ и просто неправильный символ, одновременно или разбить, еслир разбить то как, вообщем моя теория пока что такая, не судите строго я то новичок. Посоветуйте если вам нетрудно.

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

См. http://en.wikipedia.org/wiki/Longest_common_subsequence_problem и, в частности, http://en.wikipedia.org/wiki/Longest_common_substring_problem.
В книге Джулиана Бакнелла «Фундаментальные алгоритмы и структуры данных в Delphi» есть реализация двух алгоритмов нахождения LCS для строк с хорошими пояснениями.

спасибо, но а на русском языке можно это прочитать, не знаешь ссылки?

http://ru.wikipedia.org/wiki/Наибольшая _общая_подпоследовательность
http://algolist.manual.ru/search/lcs/simple_lcs.php

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

После долгих поисков и раздумий я надумал что в функции должно быть, по меньшей мере три варианта решений: 1. Длины двух сравниваемых строк равны; 2. Длина искомой строки больше введенной; 3. Длина введенной строки больше искомой.
При этом если у нас (2) тогда получаем такое условие
if Length(Wright) > Length(Input) then
Wright[i] = Input[i - L];
где Wright - искомая строка, Input- введенная, L - разность позиции данного сравниваемого символа.

Если (3), то
if Length(Wright) < Length(Input) then
Wright[i] = Input[i + L];

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

К стати вот как я представляю себе прощет строк с одинаковой длиной:

Correspond := 0; // Кол-во совпавших или соответсвующих друг другу символов
if Length(Wright) = Length(Input) then
begin
for i := 1 to Length(Wright) do
begin
if Wright[i] = Input[i] then
inc(Correspond);
end;
end;
Label1.Caption := IntToStr(Trunc((Length(Wright) / Correspond) * 100));

Сравнение строк Найти похожие ветки