Разобрать текст на слова

← →
Ш-К (2007-02-26 23:25) [0]

Есть тектовый документ. Надо его распарсить на слова, выкинув все пробелы и знаки препинания.
Нужен быстый алгоритм. Быстрее того, что проверяет каждый символ на корректность.
Видел нечто похожее в JEDI - никак не могу откопать.
Задача-то распространенная. Может кто видел в базах знаний?

← →
MBo © (2007-02-27 06:42) [1]

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

← →
Думкин © (2007-02-27 06:43) [2]

> MBo © (27.02.07 06:42) [1]

Это хорошо, но автору надо:

> Быстрее того, что проверяет каждый символ на корректность.

← →
zap8 (2007-02-27 09:16) [3]

Q_ReplaceText работает быстро, можно попробовать (библитека QStrings)

← →
eXPell © (2007-02-27 09:37) [4]

у Фаранова есть такой в книге, ну почти такой: слова "распихивает" по стринггриду, сам алгоритм не помню, но скореее всего там что-то простое и по символьное сравнение, хотя кто знает)))))

ЗЫ. книга "Delphi. Программирование на языке высокого уровня", автор: Фаронов
ЗЫЫ. может быть поможет))

← →
Desdechado © (2007-02-27 10:09) [5]

> Быстрее того, что проверяет каждый символ на корректность.
Как можно, не глядя на содержание, определить, что же там содержится?

← →
Desdechado © (2007-02-27 10:10) [6]

Хотя можно строку представить потоком битов и делать логические битовые операции с масками из сторок-пробелов, строк-запятых и т.п.
Но не думаю, что это будет быстрее посимвольного сравнения.

← →
Ketmar © (2007-02-27 10:40) [7]

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

← →
GrayFace © (2007-02-27 10:48) [8]

Ш-К (26.02.07 23:25)
Нужен быстый алгоритм. Быстрее того, что проверяет каждый символ на корректность.
Помоему, ничего лучше тут не может быть. Проверяй символы на правильность с помощью массива[char] of Boolean. Главным прожегателем скорости, наверняка, будет создание строк-слов, в общем действия с уже выделенными словами.

← →
ЮЮ © (2007-02-27 10:58) [9]

Ketmar © (27.02.07 10:40) [7]

Фотку выслать :) Поставив ограничение на то, что первый символ не пробел, я не стану проверять первый символ, т.е. " не проверяя всЕ символы"

← →
Ketmar © (2007-02-27 11:05) [10]

> ЮЮ © (27.02.07 10:58) [9]
ты у меня видел слова "произвольных" и "произвольной"? я их не зря вписал.

← →
Romkin © (2007-02-27 11:12) [11]

GrayFace © (27.02.07 10:48) [8] Лучше использовать константы-множества, чем изобретать то же самое, но свое ;)
И быстрее, чем пробезать по строке, просматривая каждый символ явно не получится ;)
А вот распарсить на слова теоретически можно очень быстро, с помощью PChar, просто дать массив указателей на начало слов. Правда, все зависит от того, что потом с этим делать.

← →
TUser © (2007-02-27 11:16) [12]

Пожалуй можно, если известно, на каком языке текст. Тогда можно по началу слова предсказывать с определенной точностью его длину. Для этого у нас есть Марков. Можно сделать такое предсказание обучаемым в процессе работы, т.е. программа будет "просекать" используемую в тексте лексику. Или можно проще - давать такое предсказание на основе следней длины слова в данном тексте. Или опять-таки марков, который по длине предыдущих слов скажет длину этого. Далее, смотрим, что там, где предсказан конец слова. Если там пробел, то смотрим, что было до него. И по словарю проверяем есть ли слово нужной длины с таким началом и окончанием. Если не пробел - опять ищем в словаре слово с таким началом и серединкой. Если не нашли, - скорее всего пропущен пробел, тогда уж деваться некуда, - читаем слово целиком. При должном желании, потратив пару лет на реализацию очень быстрого поиска в словаре, обучение марковской модели, оптимизацию и изобретение всевозможных эвристических улучшений алгоритма, можно, думаю, добиться практически 100% точности определения границ слов при скорости процентов на 10, а то и на 20 выше, чем для [1]. За эти пару лет скорость процессоров возрастет на процентов 50, винчестеров - на 30, а объем памяти удвоится. Работа потянет на шнобелевскую премию по причине практической и теоретической бесполезности.

← →
TUser © (2007-02-27 11:25) [13]

> Ketmar © (27.02.07 10:40) [7]

Ну, я описал направление исследования. Только вот, что в этом человеке такого великого?

Похожие задачи встречаются у людей, которые обрабатывают какой-нибудь там геном человека. Или кишечной палочки. Например, - найти все гены в новом геноме. Но проблемы там возникают совершенно другого порядка, вот этот кусок генома, - это ген или промежуток между генами, типа пробела? И для решения приходится им изголяться и так, и эдак. Так что "найти все слова (гены) в тексте (геноме)" - задача в ряде случаев нетривиальная. И ее решение действителньо позволяет человеку задрать нос и погнуть пальцы. Только вот, никто, конечно, не заморачивается с задачами типа [0], а как законченные ламеры покупают побольше памяти и проц. (Да и невозможно это там, в отличие от разговорного языка.)

← →
Ketmar © (2007-02-27 11:47) [14]

> TUser © (27.02.07 11:25) [13]
я вёл речь конкретно про автора топика, но по причине утреннего времени написал неточно. ты уверен, что автор осилит? %-)

и потом: обрати внимание на [7]. "произвольных слов в произвольной строке".

← →
Игорь Шевченко © (2007-02-27 11:53) [15]

А вот функция DrawText в Windows как-то делает перенос по словам, и быстро. Не иначе тайный прием знает...

← →
Ketmar © (2007-02-27 11:55) [16]

> Игорь Шевченко © (27.02.07 11:53) [15]
о! кстати. ты-таки изобрёл метод. шли фотографию на постер.

← →
Джо © (2007-02-27 14:05) [17]

Свою фотографию высылать?
Метод прост, как мычание. Просим пользователя вместе со строкой ввести позиции слов в ней. Затем используем Copy. Необходимость «проверять каждый символ на корректность» отпадает.
;)

← →
shikitomedo2 © (2007-02-27 14:08) [18]

Ketmar © (27.02.07 11:55) [16]
лучше не на постер а на майку, тебе все завидовать будут

← →
Ketmar © (2007-02-27 14:35) [19]

> Джо © (27.02.07 14:05) [17]
нифига. безошибочность хромает.

> shikitomedo2 © (27.02.07 14:08) [18]
эх. лучше татуировку сделаю. "не забуду ДМ родной!" на груди -- ИШ, на спине -- АП, на голове (побрею ради такого) -- ЮЗ. можно еще на ягодицах кого-нибудь, но тут сложнее: кандидатов много.

← →
shikitomedo2 © (2007-02-27 15:03) [20]

Ketmar © (27.02.07 14:35) [19]
а нет ли свободного бицепса? на худой случай трицепса? у меня и фотка уже заготовлена (задержать может только обледенение в Далласе :( )

← →
Ketmar © (2007-02-27 15:05) [21]

> shikitomedo2 © (27.02.07 15:03) [20]
увы. на бицепсы и прочее у меня не поместится даже лицо жерты освенцима.

← →
shikitomedo2 © (2007-02-27 15:12) [22]

Ketmar © (27.02.07 15:05) [21]
жаль жаль.. а щастье было так возможно..

← →
Ketmar © (2007-02-27 15:26) [23]

так затылок ещё остаётся!

← →
shikitomedo2 © (2007-02-27 15:28) [24]

в зарослях бороды ЮЗ"а? %) буду думать

← →
Ketmar © (2007-02-27 15:55) [25]

нет, ну а какое ещё место даме предложить?

← →
Ш-К (2007-02-27 17:46) [26]

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

PS. В JEDI можно собрать из неск-х функций, но все равно будет полный перебор.

← →
Ketmar © (2007-02-27 18:40) [27]

угу. дальнейшие ускорения зависят от задачи.

← →
Romkin © (2007-02-27 19:37) [28]

Ш-К (27.02.07 17:46) [26] Да. Фактически, разбить на слова можно за один проход по строке.

> Ш-К (27.02.07 17:46) [26]

А также прикупив компьютер у которого DDR-ка вместо перфокард-ридера :)

← →
Gadenysh (2007-02-27 19:55) [31]

самый короткий алгоритм -TStrings.CommaText ))

Проверять-то все символы, конечно, надо.
Вот только количество проверок может быть много меньше количества символов.
Фотку слать?

← →
RASkov (2007-02-28 00:58) [33]

> Проверять-то все символы, конечно, надо.
> Вот только количество проверок может быть много меньше количества
> символов.

Не сходится:)

> Sha © (27.02.07 23:20) [32]
лучше траву. или грибочки. или что там ещё было?

потому как "количества символов" в чём? в ASCII? в UNICODE? в строке?

> TUser © (27.02.07 11:16) [12]

Пожалуй, нельзя. Несколько букв проверить - это несколько простых операций. Вся эта машинерия работает полюбому медленнее. Выигрыш был бы, если бы люди говорили словами длины букв по 100, ну и слова не "мутировали" бы.

Либо на ассемблере делать xlat, либо табличку плохих-хороших символов.
Это чтобы избежать сравнений символа со всеми плохими/хорошими вариантами.
То есть, классификация символа сводится к двум-трем машинным командам.

По моему у меня есть такая реализация в модуле StringConv. Он включен во многие мои пакеты на моем сайте.

Реально можно быстрее, но не на Intel платформе (хотя возможно, что в SSE* что-нибудь есть по этому повуду, но не припоминаю).
Например на IBM 360/370/... перекодировка символов в строке по таблице - одна команда. Поиск символа в строке - одна команда. Итого можно за считаное количество команд найти начало-конец слова.
Это, к слову, почему неправильно сравнивать процессоры по количеству исполняемых команд за единицу времени.

> Например на IBM 360/370/... перекодировка символов в строке
> по таблице - одна команда.

Стоп. А адрес таблицы загрузить? :)

Адрес таблицы указывается в команде. Зачем его куда-то грузить?
Там 16 регистров и от каждого (кроме R0) можно указать смещение до 4095.

Да, действительно, это я напутал.

Разобрать текст на слова Найти похожие ветки