Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

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

Tifon © (2007-02-09 15:44:00)
День добрый! Подскажите пожалуйста возможно ли сделать функцию сравнения двух слов (в моем случае слов) и установить их соответствие, не смотря на то что в слове может быть допущена орфографическая ошибка или вставлено или добавлено слово? Ни как не могу предумать подходящего алгоритма, подскажите кто что знает.

Tifon (2007-02-16 14:13:00) [1]
Спасибо, 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));

Zeqfreed (2007-02-13 17:44:00) [2]
http://ru.wikipedia.org/wiki/Наибольшая_общая_подпоследовательность
http://algolist.manual.ru/search/lcs/simple_lcs.php

Tifon (2007-02-13 17:34:00) [3]
спасибо, но а на русском языке можно это прочитать, не знаешь ссылки?

Zeqfreed (2007-02-13 17:32:00) [4]
См. http://en.wikipedia.org/wiki/Longest_common_subsequence_problemи, в частности, http://en.wikipedia.org/wiki/Longest_common_substring_problem.
В книге Джулиана Бакнелла «Фундаментальные алгоритмы и структуры данных в Delphi» есть реализация двух алгоритмов нахождения LCS для строк с хорошими пояснениями.

Tifon (2007-02-13 17:13:00) [5]
>А ты пробовал воспользоваться 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 или может сначала должна нарасчиваться только переменная сдвигания порядка, тут я еще точно не знаю)}.
Здесь я тоже еще пока что не уверен как пропускать проверку, сделать проверку на вставленный и пропущенный символ и просто неправильный символ, одновременно или разбить, еслир разбить то как, вообщем моя теория пока что такая, не судите строго я то новичок. Посоветуйте если вам нетрудно.

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

Tifon (2007-02-13 14:23:00) [6]
Чесно говоря, чувствую себя проным тупицой:(. А что такое Speller? Если это функция сравнения при которой только ошибка в одной букве может быть исправленна, то она мне не подходит, я хочу придумать, если возможно, то с вашей помощью, что-то динамичное, которое смогло б сравнивать слова независимо от их исправлений.

Elen (2007-02-12 17:04:00) [7]

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

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

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

vasIZmax (2007-02-09 17:49:00) [9]

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

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

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

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

Tifon (2007-02-09 17:27:00) [10]
>Сам-то ты понял что сказал ?)
Извините, просто из-за этой проблемы эти слова все время крутятся в голове, иногда путаюсь.

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

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

Desdechado (2007-02-09 17:19:00) [11]
В кладовке Kerk выкладывал.

Сергей М. (2007-02-09 17:05:00) [12]

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

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

Tifon (2007-02-09 16:19:00) [13]
а как он выражен, где его искать? или может уже есть такая функция?
Я нашел функцию AnsiSameStr, но она просто сравнивает без всяких соответствий и вообще, наверно с помощью обычного "If"'а:(

unknown (2007-02-09 16:16:00) [14]

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

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

Tifon (2007-02-09 16:06:00) [15]
а что такое SoundEx?

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

unknown (2007-02-09 15:52:00) [16]

>
> Tifon © (09.02.07 15:44)

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

TRUNK (2007-02-09 15:52:00) [17]
Вычислить коэффициент "похожести" двух слов и сравнить его с неким пороговым значением. Коэффициент вычисляем как процент совпадающих букв (одинаковых букв в одинаковых позициях). Правда, если слова будут отличаться по длине, надо будет придумать алгоритм посложнее...

fd979 (2007-02-09 15:51:00) [18]
Можно установить процент соответствия

alles (2007-02-09 15:51:00) [19]
function IsEqualStrings(s:string; s1:string): boolean;
begin
Result:= s=s1;
end;

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »