Forth http://fforum.winglion.ru/ |
|
*поиск частых последовательностей слов http://fforum.winglion.ru/viewtopic.php?f=19&t=2138 |
Страница 1 из 2 |
Автор: | mOleg [ Вт июн 09, 2009 03:26 ] |
Заголовок сообщения: | *поиск частых последовательностей слов |
задан исходный текстовый файл (не важно какой - книга, исходник программы) найти наиболее часто встречающиеся последовательности состоящие из двух и более слов, при этом слова могут находиться в разных строчках. Словами считать любую последовательность символов, не содержащих пробельные символы. результат обработки вывести в файл в виде: NNNNN последовательность где NNNNN десятичное число - абсолютное количество повторений, а "последовательность" - строка из повторяющихся слов, разделенных пробелом. P.S. необходимо считать все возможные варианты последовательностей, к примеру, если в тексте встречаются строчки Цитата: Вася пошел гулять
Вася пошел гулять Вася пошел сочетание "Вася пошел" должно быть посчитано трижды, а "Вася пошел гулять" дважды. |
Автор: | Гость [ Вт июн 09, 2009 07:39 ] |
Заголовок сообщения: | |
Quote: Вася пошел гулять Вася пошел гулять Вася пошел сочетание "Вася пошел" должно быть посчитано трижды, а "Вася пошел гулять" дважды. тут и более длинные фразы есть: Вася пошел гулять Вася пошел - 2 раза Вася пошел гулять Вася - 2 раза пошел гулять Вася пошел - 2 раза и тд и тп |
Автор: | garbler [ Вт июн 09, 2009 10:16 ] |
Заголовок сообщения: | |
что делать, если повторов только один? вася пошел бегать вася пошел прыгать вася пошел вася пошел бегать что должно быть тут, выводить (00001 "вася пошел прыгать") ? |
Автор: | VshMt [ Вт июн 09, 2009 16:08 ] |
Заголовок сообщения: | |
(00002 "вася пошел бегать") Повторов то > 1 |
Автор: | VshMt [ Вт июн 09, 2009 16:44 ] |
Заголовок сообщения: | |
Что-то подобное по поиску максимальных повторяющихся последовательностей видел в описании APL. 1. Составить словарь текста. 2. Закодировать текст ч\з индексы, заменив все лишние символы перевода строки на пробелы (переносы?) (или не кодировать а сравнивать символьно?) 3. сгенерировать список (отсортированный) с нарезкой кодированного текста по х слов. (кол-во эл-в = кол-во слов в тексте - х) 4. посчитать сколько одинаковых последовательностей. выбрать с максимальным кол-м повторов. 5. 3 и 4 в цикле по х (от n до m) и выбрать максимум повторов.... Можно без 1 и 2. |
Автор: | вопрос [ Вт июн 09, 2009 18:05 ] |
Заголовок сообщения: | |
Anonymous писал(а): Quote:
Вася пошел гулять Вася пошел гулять Вася пошел сочетание "Вася пошел" должно быть посчитано трижды, а "Вася пошел гулять" дважды. тут и более длинные фразы есть: Вася пошел гулять Вася пошел - 2 раза Вася пошел гулять Вася - 2 раза пошел гулять Вася пошел - 2 раза и тд и тп Интересно посчитать, что в этом плане может дать комбинаторика, как бы автору программы не оказаться в роли султана, который оплачивал изобретение шахматной доски |
Автор: | garbler [ Вт июн 09, 2009 18:17 ] |
Заголовок сообщения: | |
никаких султанов тут не будет, ибо это обычное BWT преобразование. разве что можно использовать тот факт, что работа идёт со словами (что проще), а не с подстроками. p.s. собственно, если запретить вывод цепочек слов по одному совпадению, то к BWT придётся ещё фильтр простенький "дорисовать" (с линейной сложностью) to VshMt: вот об этом и был мой вопрос, а вовсе не о том, о чём ты подумал. |
Автор: | mOleg [ Вт июн 09, 2009 19:13 ] |
Заголовок сообщения: | |
если выражение встречается единожды, оно не выводится. Речь идет только о повторах (2 и более раз) Возможно имеет смысл оставить возможность выбирать максимальную длину последовательности слов, ограничив, скажем 10-ю словами. Но этот вопрос оставлен на усмотрение взявшегося решать |
Автор: | VshMt [ Ср июн 10, 2009 10:22 ] |
Заголовок сообщения: | |
garbler Цитата: o VshMt: вот об этом и был мой вопрос, а вовсе не о том, о чём ты подумал.
Я без подковырок, серьезно. О чем я подумал не о том о чем ты спросил? Вроде решение есть. Оно наверное неидеальное а может и неправильное. Просто сама идея в APL мне оченно понравилась. Там удобно сделана работа с массивами (разбиение, сортировки и т.п.) и такая вот задача решается на раз... Примерно как-то так... о BWT Код: Вкратце, процедура преобразования происходит так:
1) выделяется блок из входного потока, 2) формируется матрица всех перестановок, полученных в результате циклического сдвига блока, 3) все перестановки сортируются в соответствии с лексикографическим порядком символов каждой перестановки, 4) на выход подается последний столбец матрицы и номер строки, соответствующей оригинальному блоку. Я уже старый грузинский пенсионер и не вкурил о связи BWT с исходной задачей... Ну сжатие.. |
Автор: | garbler [ Ср июн 10, 2009 15:46 ] |
Заголовок сообщения: | |
to VshMt: код, иллюстрация того, что я сказал (если меня mOleg забанит, то это будет твоя вина), работает так: http://pastebin.com/f623ee965 (походу выяснилась ещё одна особенность, операции над строками следует делать "short circuit" http://pastebin.com/f93deebc иначе тормозит) для строки:
Вася пошел гулять Вася пошел
3: Вася пошел 2: гулять Вася пошел 2: пошел гулять Вася пошел вот это и было BWT преобразование, а о MTF и арифметическом кодировании (а ещё лучше range coder) я бы поговорил в другой раз p.s. если кто перла не знает, то, вкратце, там так:
2) составляем список смещений на слова (каждое смещение однозначно определяет строку) 3) сортируем по первому столбцу (в BWT столбец задаётся принимаемой моделью текста) 4) проходим по окончательной таблице и считаем повторяющиеся префиксы, выводим те из них, что содержат пробелы и наличествуют более одного раза p.p.s. поскольку все близкие префиксы сгруппированы, то достаточно только одного финального прохода p.3.s. решение на форте было бы увидеть гораздо интереснее, т.к. просматриваются работа со строками и динамические структуры данных (а так-же итераторы к ним) |
Автор: | garbler [ Ср июн 10, 2009 16:23 ] |
Заголовок сообщения: | |
mOleg писал(а): да, было бы гораздо интереснее код на Форте бы увидеть этого решения
подозреваю, что тебе это надо для оптимизатора, так что статистику фортовских исходников по большой базе я бы тоже не отказался посмотреть |
Автор: | mOleg [ Ср июн 10, 2009 16:27 ] |
Заголовок сообщения: | |
garbler писал(а): подозреваю, что тебе это надо для оптимизатора, так что статистику фортовских исходников по большой базе я бы тоже не отказался посмотреть
не угадал просто попалась интересная задачка для конкурса (причем давно ничего не выкладывалось сюда) а уж для чего использовать - это вопрос второй |
Автор: | mOleg [ Пт июн 12, 2009 17:17 ] |
Заголовок сообщения: | |
ладно, мне лень ждать остальных, поэтому выкладываю свой вариант. код написан для форка (последней версии) тут лежит нужная, но отсутствующая в форке библиотека spells.fts <pre> \ 09.06.2009 ~mOleg \ Сopyright [C] 2009 mOleg mininoleg@yahoo.com \ поиск часто встречающихся последовательностей слов длиной от двух и более os/ spells.fts os/ file-add.fts memory/ buff.fts branch/ for-next.fts vocs/ vocadd.fts transl/ numbers.fts 2 VALUE chains# \ определяет сколько слов в цепочке должно быть(минимум) 2 VALUE replies# \ определяет сколько повторов надо искать 0 VALUE pbuff \ буфер для хранения просматриваемого текста VARIABLE obtained \ количество полученных совпадений в текущем проходе \ создать промежуточный буфер : crBuff ( --> ) SOURCE NIP 2 * Buffer TO pbuff ; \ создать словарь в хипе с именем asc # сделать его текущим и контекстным : HVOC ( asc # --> ) ALSO HEAP DEFINITIONS DDUP SVOCAB EVAL-TOKEN DEFINITIONS ; \ добавить новое слово с именем, определяемым asc # в текущем словаре \ при выполнении имя должно возвращать количество повторов и собственно само имя : new-word ( asc # --> xt ) CREATED 1 , LAST A@ DUP ID>ASC , , LINK>C ( # addr --> ) DOES> OVER IFNOT NIP CELL + D@ TYPE SPACE ;THEN TUCK @ > IFNOT DUP @ N. SPACE CELL + D@ TYPE CR ;THEN DROP ; \ добавить в текущий словарь определение с именем asc # \ если слово уже есть в словаре, увеличить счетчик на 1 : +word ( asc # --> xt ) DDUP GET-CURRENT SEARCH-WORDLIST IF 1 OVER CFL + +! NIP NIP ;THEN new-word ; \ преобразовать последовательность токенов в последовательность слов, \ вывести в STDOUT : ~chain ( addr # --> ) ADDR / FOR 0 OVER A@ EXECUTE ADDR + TILL DROP ; \ создание слова с именем, содержащим последовательность слов : new-chain ( addr # --> ) CREATED 1 , LAST A@ ID>ASC , , ( # addr --> ) DOES> TUCK @ > IFNOT 1 obtained +! DUP @ N. CELL + D@ ~chain CR ;THEN DROP ; \ : +chain ( addr # --> ) DDUP GET-CURRENT SEARCH-WORDLIST \ addr # xt imm | 0 IF CFL + 1 SWAP +! DDROP ;THEN new-chain ; \ поиск одинаковых последовательностей : search ( # --> ) DUP >L 0x0A {# S>D #S s" REPS" HOLDS #> HVOC \ --> # pbuff Buffer> CELL / L@ - 1 + 0 MAX FOR DUP L@ CELLS +chain CELL + TILL DROP LDROP ; \ вывести собранную статистику : ~ws ( # --> u ) obtained OFF >R GET-CURRENT LAST-NAME BEGIN *WHILE R@ OVER LINK>C EXECUTE LINK> REPEAT RDROP DROP obtained @ ; \ собрать статистику по количеству повторений и вывести ее на экран : stat ( --> ) pbuff Buffer> NIP CELL / 1 - chains# BEGIN OVER WHILE DUP search replies# ~ws DUP WHILE ." \n\r всего найдено: " N. ." совпадений для последовательностей длиной в: " DUP N. ." слов\n\r" UMOUNT \ освобождение памяти -1 0 D+ REPEAT THEN DROP BYE ; VOCABULARY RMCOMM \ словарь с коментариями ALSO RMCOMM DEFINITIONS ALIAS ( ( IMMEDIATE ALIAS \ \ IMMEDIATE \ сюда можно добавлять и другие варианты коментариев RECENT \ уборка встречаемых коментариев : skip-comments ( asc # --> asc # TRUE | FALSE ) DDUP [ ALSO RMCOMM CONTEXT A@ LIT, ] SEARCH-WORDLIST IF EXECUTE DDROP FALSE ;THEN TRUE ; VECT -COMMENTS ' TRUE IS -COMMENTS \ разобрать входной поток на слова \ собрать статистику по частоте употребления слов (и самим словам) :> transform ( --> ) crBuff s" dict" HVOC BEGIN NEXT-WORD *WHILE -COMMENTS IF +word SP@ 4 pbuff >Buffer DDROP THEN REPEAT DDROP ; \ -- опции командной строки ---------------------------------------------------- \ взять десятичное число из входного потока, вернуть его численное значение : getnum ( / number --> n ) NEXT-WORD 0x0A S>VAL IFNOT ERROR" Ожидается числовой параметр!" THEN DROP ; \ неопознанный ключ считаем именем входного файла SECRET: NOTFOUND ( / asc # --> ) <BACK ParseFileName DDUP ." \n\rОткрываю: " TYPE CR ['] FileSource CATCH IF ERROR" Неверное имя файла!" THEN transform EvalSrcWith ;S \ определить минимальное количество повторов SPELL: -r ( / number --> ) getnum TO replies# ;S \ определить минимальное количество слов в цепочке SPELL: -c ( / number --> ) getnum TO chains# ;S \ если не надо учитывать коментарии в тексте (Форт-коментарии!) SPELL: -f ( --> ) ['] skip-comments IS -COMMENTS ;S \ помощь по использованию программы SPELL: /? ( --> ) ." \n\rreplyes.exe [-f] [-c n] [-r n] filename [>outfile]" ." \n\rв квадратных скобках необязательные параметры." ." \n\r -f - говорит о том, что из текста надо убирать коментарии" ." \n\r -r n - используется с числовым параметром, определяющим" ." \n\r\t с какого количества повторов собирать статистику" ." \n\r -c n - используется с числовым параметром, определяющим" ." \n\r\t минимальное количество слов в искомой последовательности" ." \n\r outfile нужен, если результат работы хочется сохранить в файл" BYE ;S \ EOF -- дальше сохранение кода идет ------------------------------------------- SET-OPTIONS ' stat IS Completion \ задать действие по завершению обработки коммандной строки s" Сохранение " TYPE s" replyes.exe" DDUP TYPE SAVE s" завершено успешно.\n\r" TYPE BYE </pre> |
Автор: | mOleg [ Пт июн 12, 2009 17:22 ] |
Заголовок сообщения: | |
да, вариантов решения может быть много. Я использовал словари. Выше предложенный вариант с перловским примером прочитал только сейчас ранее специально не заглядывал. Выбранный мною алгоритм не быстр и прожорлив в отношении памяти, но есть возможность значительно ускорить его. Вобщем, надеюсь, что мое решение не окажется единственным |
Автор: | mrack [ Сб июн 13, 2009 05:52 ] |
Заголовок сообщения: | |
для SPF4 Код: STARTLOG REQUIRE "" devel/~ac/lib/str5.f \ -------- раздел подготовка текста ----------- \ увеличить на единицу 'adr' и добавить в него символ с кодом 'c' : add_chr ( c adr -- adr ) 1+ SWAP OVER C! ; \ добавить символ с кодом 'c' в позицию 'adr+1' \ если это пробел или перевод строк то добавить пробел если его там нет : add_chr? ( c adr -- adr ) >R DUP DUP DUP DUP 32 = >R 10 = >R 13 = >R 9 = R> R> R> + + + R> SWAP IF >R R@ C@ 32 = R> SWAP IF NIP ELSE NIP 32 SWAP add_chr THEN ELSE add_chr THEN ; \ переработать строку 's1' в строку 'adr' убрав переводы строк и лишние пробелы : prpr_txt ( s1 -- s1 adr ) CR CR ." входной текст:" CR DUP STR@ 2DUP TYPE DUMP DUP STR@ DROP ALLOCATE THROW 2DUP SWAP STR@ ROT 32 SWAP add_chr 1- BEGIN >R OVER C@ R> add_chr? >R 1- DUP 0 = >R SWAP 1+ SWAP R> R> SWAP UNTIL DROP 2DROP CR CR ." переработанный текст:" 2DUP SWAP STR@ NIP 2DUP CR TYPE DUMP ; \ -------- раздел выделение груп слов --------- \ вернуть не ноль если в 'adr u' есть пробел : wrds? ( adr u -- i ) 1 - 0 BEGIN >R OVER C@ 32 = R> SWAP IF DROP TRUE THEN >R DUP 0= >R 1 - SWAP 1 + SWAP R> R@ + R> SWAP UNTIL NIP NIP ; \ вернуть неноль если 'adr u' ограничен пробелами 'с наружи' и имеет хотябы один пробел внутри : wrd_gr? ( adr u -- i ) 2DUP wrds? >R OVER + C@ SWAP 1 - C@ 32 = SWAP 32 = * R> * ; \ временый буфер хранения адресов найденых групп 0x1000 ALLOCATE THROW VALUE tmp_b \ сброс 'верхнего' значения 'tmp_b' и уменьшение счетчика на единицу : tmp_b_drop ( -- ) tmp_b @ 1 - DUP tmp_b ! 4 * tmp_b DUP 8 + SWAP 4 + ROT MOVE ; \ сброс n-го адреса буфера 'tmp_b' : tmp_b_drop_n ( n -- ) tmp_b DUP @ DUP 1 - SWAP >R OVER ! \ n adr \ n2 DUP >R 2DUP SWAP 4 * + >R SWAP 1 + 4 * + R> R> R> 4 * + OVER - MOVE ; \ получить адрес 'n' из буфера 'tmp_b' : tmp_b_n@ ( n -- adr ) 4 * tmp_b + @ ; \ получить 'ерхний' адрес из буфера 'tmp_b' : tmp_b@ ( -- adr ) 4 tmp_b + @ ; \ искать в тексте группы длинной 'l', сложить адреса начал груп и количество их в масив 'tmp_b' : srch_grp_l ( adr u l -- ) CR CR ." начат поиск груп слов длиннной '" DUP . ." ' символов в области: '" >R 2DUP SWAP . . R> ." '" DUP >R - SWAP R> 0 tmp_b 4 + \ u adr l k tmp_b BEGIN >R >R >R DUP R@ wrd_gr? R> R> ROT R> SWAP IF >R 1 + >R >R DUP R> R> ROT R@ ! R> 4 + THEN >R >R >R SWAP DUP 0= >R 1 - SWAP 1 + R> R> R> ROT R> SWAP UNTIL DROP NIP NIP NIP tmp_b ! ." найдено '" tmp_b @ . ." ' групп" ; \ -------- анализ совпадения груп --------------------------------- \ сравнить строку длиной 'l' и началами в буфере 'tmp_b' с остальными и выдать количекство совпадений : srch_cmpr ( l -- ) CR CR ." поиск совпадений в списке фраз:" tmp_b @ 0 DO CR I 1 + DUP . 4 * tmp_b + @ OVER TYPE LOOP 0 tmp_b @ 1 - BEGIN DUP 1 + tmp_b_n@ SWAP >R SWAP >R SWAP >R R@ tmp_b@ R@ COMPARE 0= R> R> ROT R> SWAP IF SWAP 1 + SWAP DUP 1 + tmp_b_drop_n 1 - THEN 1 - DUP 1 < UNTIL DROP SWAP CR CR ." группа слов длиной: '" DUP . ." ' символов '" tmp_b@ SWAP TYPE ." ' повторяется '" . ." ' раз(а)" CR ; \ анализ совпадающих груп : rpt_gr. ( l -- ) BEGIN tmp_b @ 1 > WHILE DUP srch_cmpr tmp_b_drop REPEAT DROP ; \ -------- итого программа --------------------------------------- : search_rpt_grp " { S' test.txt' FILE}" prpr_txt \ здесь указать файл с текстом на анализ SWAP DUP >R STR@ NIP DUP R> STRFREE BEGIN >R 2DUP R@ srch_grp_l R@ rpt_gr. R> 1- DUP 3 < UNTIL 2DROP DROP ; search_rpt_grp |
Страница 1 из 2 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |