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

← →
Ш-К (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] Да. Фактически, разбить на слова можно за один проход по строке.

← →
Ketmar © (2007-02-27 19:39) [29]

> Romkin © (27.02.07 19:37) [28]
не "можно", а "нужно"! %-)

← →
TUser © (2007-02-27 19:43) [30]

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

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

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

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

← →
Sha © (2007-02-27 23:20) [32]

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

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

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

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

← →
Ketmar © (2007-02-28 04:08) [34]

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

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

← →
TUser © (2007-02-28 04:42) [35]

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

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

← →
Alex Konshin © (2007-02-28 04:43) [36]

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

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

← →
Alex Konshin © (2007-02-28 04:51) [37]

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

← →
Джо © (2007-02-28 05:06) [38]

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

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

← →
Alex Konshin © (2007-02-28 05:12) [39]

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

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

Там, правда, для команды перекодировки было ограничение длины 256 байт.
Но не помню уже, возможно в XA или 390 была добавлена команда для перекодировки длинных строк типа MVCL,CLCL.

> Ketmar © (28.02.07 04:08) [34]
> лучше траву. или грибочки. или что там ещё было?

как регулярно принимаешь?

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

начинай метлы юзать )

> RASkov (28.02.07 00:58) [33]
>> Проверять-то все символы, конечно, надо.
>> Вот только количество проверок может быть много меньше количества
>> символов.

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

выходит, что s / t > 1,
где s - количество символов в строке, t - количество сравнений

Может так че-нить щелкнет? )

> RASkov (28.02.07 00:58) [33]

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

> Sha © (28.02.07 09:19) [42]
да с удовольствием. причём метлу, наверное, придётся съесть. иначе я пост так и не пойму. можно "на пальцах", а? специально для дворников?

> Sha © (28.02.07 09:36) [44]
хм. ты намекаешь на интерпретацию строки как набора word"ов, например? если да, то не надо спешить с фотографией. всё равно это проверяет все символы строки.

> Ketmar © (28.02.07 12:18) [46]
нет, он намекает на что-то Бойеро-Муровско-подобное, но что именно - ума не приложу - алгоритм Бойера-Мура тут не подойдет....
будем есть метлы вместе :)

> Ketmar © (28.02.07 12:18) [46]

О том и речь, что проверены будут все символы,
но количество проверок меньше количества символов.

ЗЫ А фотку с метлой пришли )

> Sha © (28.02.07 12:39) [48]
да сколько угодно проверок. я-то говорил не про количество проверок, а про то, что все символы проверять надо. %-) хоть ты SSE заюзай -- всё равно проверять все.

зыж а вот не пришлю. потому что гад.

> wicked © (28.02.07 12:33) [47]
неа. насколько я понял -- array [Word] и ты ды. действительно, проверок меньше. но смысл от этого не меняется -- что байты проверять, что слова, что двойные слова...

кстати, ещё неизвестно, что быстрее: по символам или по таблице в 64 кила, которая загадит кэш. %-)

> Ketmar © (28.02.07 12:44) [50]
я вот думаю - а мы собрались молотить гигабайты в секунду?...
на современных мощностях простой автомат на два состояния с табличкой плохих/хороших символов позволит молотить мегабайты и десятки мегабайт в секунду... и узким местом там будет не сам разбор, а "подвоз патронов" - ввод и вывод данных...
а 64к табличка, афаир, вся в кеш влезет и еще место будет - так что и иероглифы молотить можно

> wicked © (28.02.07 12:43) [49]

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

> Ketmar © (28.02.07 12:44) [50]
> да сколько угодно проверок. я-то говорил не про количество проверок...

а всплеск эмоций Ketmar © (28.02.07 04:08) [34] был наверно по поводу
того что "всё равно проверять все" )))

> кстати, ещё неизвестно, что быстрее

это да

> wicked © (28.02.07 12:52) [51]
> узким местом там будет не сам разбор, а "подвоз патронов" - ввод и вывод данных...

Совершенно верно.
Иногда бывает, что разница в скорости стрельбы и скорости "отвоза" превышает порядок.
И здесь, похоже, тот самый случай.

> wicked © (28.02.07 12:52) [51]
вместо этой таблички можно что-нибудь полезное туда положить. %-)

> Sha © (28.02.07 12:57) [52]
по поводу криво сформулированной фразы. и нескольких литров крепкого пива внутри Кэтмара. %-)

и вообще -- может, на меня яркий цвет значка так действует? может, я завидую?! %-)

> Sha © (28.02.07 13:09) [53]
> Иногда бывает, что разница в скорости стрельбы и скорости
> "отвоза" превышает порядок.
так мы, по-моему, давно уже обсуждаем сферического коня. %-)

> Ketmar (28.02.2007 12:16:45) [45]

Количество символов не зависит от длины символа.

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