Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Пт мар 29, 2024 01:32

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




Ответить
Имя пользователя:
Заголовок:
Текст сообщения:
Введите текст вашего сообщения. Длина сообщения в символах не более: 60000

Размер шрифта:
Цвет шрифта
Настройки:
BBCode ВКЛЮЧЕН
[img] ВЫКЛЮЧЕН
[flash] ВЫКЛЮЧЕН
[url] ВКЛЮЧЕН
Смайлики ВЫКЛЮЧЕНЫ
Отключить в этом сообщении BBCode
Не преобразовывать адреса URL в ссылки
Вопрос
Теперь гостю придется вводить здесь пароль. Не от своей учетной записи, а ПАРОЛЬ ДЛЯ ГОСТЯ, получить который можно после регистрации на форуме через ЛС.:
Этот вопрос предназначен для выявления и предотвращения автоматических регистраций.
   

Обзор темы - *поиск частых последовательностей слов
Автор Сообщение
  Заголовок сообщения:   Ответить с цитатой
Млин :evil: Ктонить внятно объяснит? А то то что в примерах BWT как-то неблизко к моему пониманию топика.... А понять хотца... Несмотря на то что я программер-пенсионер :lol: Зато растет подрастающее поколение, может в свое время ему объясню...
Сообщение Добавлено: Чт июн 18, 2009 11:49
  Заголовок сообщения:   Ответить с цитатой
оффтопик... представьте свой личный тигроловный флот, сэр,
а потом и делайте подобные заявления, но только не в подобных темах.
Сообщение Добавлено: Чт июн 18, 2009 04:20
  Заголовок сообщения:   Ответить с цитатой
Ы:)
модное масковское слово "тупо" происходит от древнего абхазского обычия "ловить горных тигров сачком". (с) КВН
ну вот примерно как ловля тигров сачком выгллядят конкурсы по решению задач на форз форуме :)
Сообщение Добавлено: Чт июн 18, 2009 00:16
  Заголовок сообщения:   Ответить с цитатой
Код:
Анализ строк
String Search
Graham A. Stephen
October 1992


Анализ строк
Сообщение Добавлено: Вт июн 16, 2009 14:04
  Заголовок сообщения:   Ответить с цитатой
mOleg писал(а):
кстати, наблюдение за работой позволяет сделать вывод, что просто поиск одинаковых последовательностей для анализа кода практически бесполезен

анализ кода производится в разных целях, если стоит задача - понять систему, то, разумеется, вещи аналогичные Imagix 4D будут более приемлемыми. если стоит задача - отладить оптимизатор, то инструментарий будет другим. если стоит задача - определить степень заимствований или лицензионную чистоту - третьим.

mOleg писал(а):
Необходимо как минимум, не включать в статистику более короткие последовательности, если они являются составной частью длинных

требуемые данные извлекаются из уже имеющегося отчёта, пример:
    15 Вася пошёл гулять
    16 Вася пошёл
ясно, что короткая последовательность сама по себе встречается только 1 раз

mOleg писал(а):
искать не точные последовательности, а похожие последовательности

достаточно переписать функцию сравнения в сортировщике (например, выдавать метрику Левенштейна для двух строк)
Сообщение Добавлено: Вт июн 16, 2009 11:15
  Заголовок сообщения:   Ответить с цитатой
Anonymous писал(а):
Google: BWT алгоритм
и читаем хоть начиная с википедии:)


Не ну точно все такие вумные как вутки...

Wiki писал(а):

Краткое описание, решаемые задачи
Преобразует повторяющиеся подстроки во входном тексте в идущие подряд последовательности одинаковых символов в выходном.


Пожалей старика ;) разжуй... А то я че то никак не вкурю...
Сообщение Добавлено: Пн июн 15, 2009 20:58
  Заголовок сообщения:   Ответить с цитатой
Цитата:
кстати, наблюдение за работой позволяет сделать вывод, что просто поиск одинаковых последовательностей для анализа кода практически бесполезен. Необходимо как минимум, не включать в статистику более короткие последовательности, если они являются составной частью длинных, во-вторых, искать не точные последовательности, а похожие последовательности, то есть похоже на уже бывшую тут задачу поиск похожих имен слов Вот.
НУ. есть такая штука как макроподстановщик - он как мне представляется именно этим и занят, только на самом низком уровне.
Сообщение Добавлено: Пн июн 15, 2009 20:27
  Заголовок сообщения:   Ответить с цитатой
кстати, наблюдение за работой позволяет сделать вывод, что просто поиск одинаковых последовательностей для анализа кода практически бесполезен. Необходимо как минимум, не включать в статистику более короткие последовательности, если они являются составной частью длинных, во-вторых, искать не точные последовательности, а похожие последовательности, то есть похоже на уже бывшую тут задачу поиск похожих имен слов Вот.
Сообщение Добавлено: Пн июн 15, 2009 19:04
  Заголовок сообщения:   Ответить с цитатой
VshMt писал(а):
Я так вас понял BWT это алгоритм составления словаря по частоте и наибольшей длине повторения? Что в BWT является числом повторений конкретного блока?


Google: BWT алгоритм
и читаем хоть начиная с википедии:)
Сообщение Добавлено: Пн июн 15, 2009 15:35
  Заголовок сообщения:   Ответить с цитатой
mOleg можно спросить в этой ветке?

Слушайте garbler я весь моск сломал:) В Перле я ни бумбум. Я так вас понял BWT это алгоритм составления словаря по частоте и наибольшей длине повторения? Что в BWT является числом повторений конкретного блока?
Сообщение Добавлено: Пн июн 15, 2009 13:15
  Заголовок сообщения:   Ответить с цитатой
Возможные перспективы развития/применения решения данной задачи:)

[url=http://www.visti.net/~dwl/art/dz/] ГЛУБИННЫЙ АНАЛИЗ ТЕКСТОВ
ТЕХНОЛОГИЯ ЭФФЕКТИВНОГО АНАЛИЗА ТЕКСТОВЫХ ДАННЫХ
[/url]
Сообщение Добавлено: Пн июн 15, 2009 09: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
Сообщение Добавлено: Сб июн 13, 2009 05:52
  Заголовок сообщения:   Ответить с цитатой
да, вариантов решения может быть много. Я использовал словари. Выше предложенный вариант с перловским примером прочитал только сейчас 8) ранее специально не заглядывал. Выбранный мною алгоритм не быстр и прожорлив в отношении памяти, но есть возможность значительно ускорить его. Вобщем, надеюсь, что мое решение не окажется единственным 8)
Сообщение Добавлено: Пт июн 12, 2009 17:22
  Заголовок сообщения:   Ответить с цитатой
ладно, мне лень ждать остальных, поэтому выкладываю свой вариант.
код написан для форка (последней версии)
тут лежит нужная, но отсутствующая в форке библиотека 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>
Сообщение Добавлено: Пт июн 12, 2009 17:17
  Заголовок сообщения:   Ответить с цитатой
garbler писал(а):
подозреваю, что тебе это надо для оптимизатора, так что статистику фортовских исходников по большой базе я бы тоже не отказался посмотреть

не угадал 8)
просто попалась интересная задачка для конкурса (причем давно ничего не выкладывалось сюда)
а уж для чего использовать - это вопрос второй
Сообщение Добавлено: Ср июн 10, 2009 16:27

Часовой пояс: UTC + 3 часа [ Летнее время ]


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB