Перебор текста по словарю

← →
_mik © (2006-07-19 19:09) [40]

фактически шаблон выглядит так
"$*слово*"
причем обобщающих символов может и не быть
например:
"*слово"
или
"$слово*"
"$слово"
"слово"
"$*слово"
ну и тп.

где символ $ означает сравнение с учетом регистра,
да и еще "*" могут распологатся только в начале, либо в конце слова!

← →
Pavia © (2006-07-19 19:55) [41]

Нет проблем ты когда строку разбираешь на слова. Ты затем будешь перебирать все варианты слова, которые можешь составить из данного слова путем удоления нескольких символов с начала или с конца. N*(N-1)/2 вариантов.
И еще совет откажись от класса TStringList.

← →
Romkin_ (2006-07-19 20:16) [42]

Pavia © (19.07.06 19:55) [41] Обычно, когда говорят "откажись", указывают альтернативу ;)
_mik © (19.07.06 19:09) [40] Так * - это начало слова? Или текста?
почему нельзя вместо * ставить пробел?
Если убрать *, то у тебя словарь распадается на три, префиксов, суффиксов и подстановок слов?

← →
_mik © (2006-07-19 20:44) [43]

звездочка означает любое количество символов перед или после слова
в зависимости от того где стоит,
если ее нет, то
значит слово в словаре должно полностью соответствовать слову в тексте!

← →
_mik © (2006-07-19 20:45) [44]

> Нет проблем ты когда строку разбираешь на слова. Ты затем
> будешь перебирать все варианты слова, которые можешь составить
> из данного слова путем удоления нескольких символов с начала
> или с конца. N*(N-1)/2 вариантов.
> И еще совет откажись от класса TStringList.

а как же быть когда в словаре есть слово с двумя "*" в начале и в конце?

← →
Ketmar © (2006-07-19 22:12) [45]

>_mik © (19.07.06 19:09) [40]
простейший фильтр.

← →
Pavia © (2006-07-19 23:38) [46]

А что с * звездочками? А я про что говорил.
Вот перебор.
function strings(s:string):string;
var i,j:Integer;
ss,ss1,ss2,ss3:string;
begin
result:="";
For i:=Length(s) downto 1 do
For j:=1 to Length(s)-i+1 do
begin
ss:=copy(s,j,i);
ss2:=Find(ss);
if ss2<>"" then
ss2:=Find("*"+ss);
if ss2<>"" then
ss2:=Find(ss+"*");
if ss2<>"" then
ss2:=Find("*"+ss+"*");
if ss2<>"" then
ss2:=Find("$*"+ss);
if ss2<>"" then
ss2:=Find("$"+ss+"*");
if ss2<>"" then
ss2:=Find("$*"+ss+"*");
if ss2<>"" then
begin
if copy(s,1,j-1)="" then ss1:=""
else ss1:=strings(copy(s,1,j-1));
if copy(s,j+i,Length(s)-j-i+1)="" then ss2:=""
else ss3:=strings(copy(s,j+i,Length(s)-j-i+1));
result:=ss1+ ss2+ss3;
exit;
end;
end;
end;
Find(ss)- поиск строки, я бы сделал через хэш таблицы.
И еще совет откажись от класса TStringList.
Медленный класс. Я бы просто использовалбы строку или строки.

← →
Romkin © (2006-07-20 11:47) [47]

_mik © (19.07.06 20:44) [43] Я правильно понял - если звездочки, то это часть слова, а если нет - слово целиком на замену?
То есть, звездочка означает ограничение буквами, ее отсутствие - ограничение разделителями (пробел, запятая и тд)?
Тогда ведь можно обобщить, заменить все разделители слов на пробел, а в словаре избавится от звездочек, присоединив к словам без звездочки пробелы. То есть "АБ" переходит в " АБ ", а "*АБ*" переходит в "АБ"?

← →
_mik © (2006-07-20 12:12) [48]

Ты не совсем правильно понял >Romkin!
да "*АБ*" означает часть слова содержащего "АБ", причем "АБ" должно быть ограничено буквами, а если звездочек не то разделителями!
Но удалять разделители я не могу, это приведет к потери части смысла текста!
(Яже пишу программу озвучивания текста)

← →
_mik © (2006-07-20 12:16) [49]

>Pavia Спасибо!
Но насколько японял, твой алгоритм онтносится примерно к O(n^2) при больших значениях!
А это я думаю врятли допустимо!
Поскольку в словаре слов со звеждочкой может быть порядка ~700-1000!
Это приведет к сильному падению быстродействия!

Я когда пытался это реализовать собственными силами делал примерно тже самое!

Хотя я попробую, наверное вечером отпишусь!

_mik © (20.07.06 12:12) [48] А никто не заставляет тебя удалять их совсем. Только на вход словаря подавай с заменой. А после замены - присоединяй. Или знаки препинания тоже преобразуются?
Вообще говоря, какой объем словаря? Можешь согласится с увеличением этого объема раз в 5-10? Если использовать дерево, то можно достичь примерно O(NlogM) по моей первой прикидке, где N - число символов текста, M - число слов в словаре... (или символов? - с утра плохо думается) Или не так, но блиизко. Но за счет объема

Спасибо за советы!
Но для деревьев я пока еще мал!
Я только начинаю вникать в основные концепции!
и некоторы вещи мне сложновато понять!

я опробовал процедуру Pavia и она дола приемлемое быстродейстиве!

PS если когото интересует компонент для подключения TTS движка на основе SAPI 4 то могу скинуть на почту!

PPS о всех результатах дольнейшей работы буду сообщать сдесь!

Вообще эта задача описана: Бакнел. "Фундаментальные алгоритмы и структуры данных в Delphi" последняя глава, сравнение текстовых файлов.
PS. Можно найти в сети.

я этоу книжку уже нашел!
сейчас дочитываю!
СПАСИБО!

Перебор текста по словарю Найти похожие ветки