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

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

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

Перебор текста по словарю [D7, WinXP]

Страницы: 1 2 3 >
_mik © (2006-07-14 22:18:00)
Сдравствуйте!

Как можно организовать быстрыйперебор теста по словарю!

Причем словарь имеет довольно большой размер ~35000 слов и словосочетаний!, причем синтаксис словаря такой:
[$][*][слово][*]=[чему то]
где
$ - учитывать ли индекс;
* - любое кол-во символов;

_mik (2006-07-20 18:09:00) [1]
я этоу книжку уже нашел!
сейчас дочитываю!
СПАСИБО!

atruhin (2006-07-20 16:08:00) [2]
Вообще эта задача описана: Бакнел. "Фундаментальные алгоритмы и структуры данных в Delphi" последняя глава, сравнение текстовых файлов.
PS. Можно найти в сети.

_mik (2006-07-20 14:22:00) [3]
Спасибо за советы!
Но для деревьев я пока еще мал!
Я только начинаю вникать в основные концепции!
и некоторы вещи мне сложновато понять!

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

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

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

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

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

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

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

_mik (2006-07-20 12:12:00) [6]
Ты не совсем правильно понял >Romkin!
да '*АБ*' означает часть слова содержащего 'АБ', причем 'АБ' должно быть ограничено буквами, а если звездочек не то разделителями!
Но удалять разделители я не могу, это приведет к потери части смысла текста!
(Яже пишу программу озвучивания текста)

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

Pavia (2006-07-19 23:38:00) [8]
А что с * звездочками? А я про что говорил.
Вот перебор.
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.
Медленный класс. Я бы просто использовалбы строку или строки.

Ketmar (2006-07-19 22:12:00) [9]
>_mik © (19.07.06 19:09) [40]
простейший фильтр.

_mik (2006-07-19 20:45:00) [10]

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

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

_mik (2006-07-19 20:44:00) [11]
звездочка означает любое количество символов перед или после слова
в зависимости от того где стоит,
если ее нет, то
значит слово в словаре должно полностью соответствовать слову в тексте!

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

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

_mik (2006-07-19 19:09:00) [14]
фактически шаблон выглядит так
'$*слово*'
причем обобщающих символов может и не быть
например:
'*слово'
или
'$слово*'
'$слово'
'слово'
'$*слово'
ну и тп.

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

Romkin (2006-07-19 18:40:00) [15]
Поясню: фактически, то, что ты хочешь, называется синтаксическим анализом, хоть и простеньким. А тут уже и алгоритны другие.

Romkin (2006-07-19 18:37:00) [16]
А. Теперь я врубился. Фактически, в словаре у тебя шаблоны, и рассматривая строку ты прилагаешь к ней все шаблоны (оптимизируя выбор), делая замену какая пойдет. Так?
Ты лучше скажи полностью постановку. Что * - любое число символов, я понял, а что такое $? И что еще есть?

_mik (2006-07-19 18:21:00) [17]
Поиск слов и словосечетаний в словаре я уже решил!
это можно сделать:

- либо бинарным поиском, что реализуется довольно просто
а скорость выполнения данной операции составляет O(log n)
- либо при помощи хэш таблиц при этом скорость будет O(1) что еще быстрее

вся загвоздка состоит в замене в тексте с использованием '*',
Например:

есть текст : "http:\\www.randex.ru"
и есть определение в словаре: "*www*=вэ вэ вэ"

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

"http:\\вэ вэ вэ.randex.ru"

Причем таких записей в словаре как "*www*=вэ вэ вэ" может быть несколько сотен!

Stanislav (2006-07-19 10:45:00) [18]
Ketmar © (18.07.06 20:41) [34]
Ага, Только не дед могроз, а стандартная поставка Windows.
atruhin © (18.07.06 18:20) [33]
Может и за день, но мы тут 5 дней уже разговариваем.

atruhin (2006-07-18 22:49:00) [19]
Автору.
Ты так и не ответил на вопрос:
> PS Не понимаю одного в задаче, на входе слово содружество
> в словаре его нет , нашли дружество запомнили, а куда девать
> со

От этого сильно зависит алгоритм и все советы. Например:
Есть предложение:
"абвгд ежзи клм"
есть слова в словаре:
*бвгд е*
*гд ежзи ел*
Что должен найти алгоритм, более длинную или с которой раньше начинается?
И что делать с первыми (пропущеными) буквами?

Ketmar (2006-07-18 20:41:00) [20]
>Stanislav © (18.07.06 09:45) [32]
> Если БД на ACCESS драйвера не нужны.
да??? ого. Дед Мороз приносит?

>atruhin © (18.07.06 18:20) [33]
нафиг не нужны. просто разговор о них зашёл. %-)

Страницы: 1 2 3 >

Наверх

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