Программа maxlcp версия 0.0.9

Проект начат 2003-08-20; Последние изменения 2004-05-31

1  Загрузка

Исполнимый файл для Win9x/2000/XP (кросс-скомпилированный под minGW): mingw/maxlcp.zip [18 Кб ]

2  Файл readme.koi

maxlcp --- поиск максимальной повторённой подстроки


ПОДДЕРЖИВАЕМЫЕ ОКРУЖЕНИЯ

http://www.gnu.org    GNU/Linux 
http://www.mingw.org  MinGW --- Minimalist GNU For Windows


КОМПИЛЯЦИЯ

Введите make (или gmake) в директории, где находятся исходные тексты
программы.


КРАТКАЯ ИНСТРУКЦИЯ

Программа maxlcp просто выдаёт координаты самой длинной повторённой
строки. Она использует суффиксный массив, построенный программой
suffsort. Алгоритм --- наивный и время выполнения может быть
пропроционально O(N*N).

У неё есть интересное применение: простой сжиматель файлов
compress.pl, включённый в дистрибутив с исходными кодами.


Условия использования описаны файле LICENSE.koi

3  Использование и сводка опций

user@computer$ ./maxlcp --help
Usage: maxlcp [OPTIONS] FILE 
Input files: FILE  FILE.ary
Output: prints the longest pair of common prefixes

  -a <name>, or           take suffix array for FILE from <name>
  --suffix-array <name>,

  -q, --quiet             do not send any messages to stderr
  -h, --help              display this help and exit
  -m, --man               display complete description
  -v, --version           display version and exit

4  Описание

user@computer$ ./maxlcp --man
<Пропущена информация, присутствующая в предыдущем разделе>


On input program requires the FILE and its suffix array FILE.ary
Suffix array should be constructed using suffsort program from
TACU (Text Analysis and Conversion Utilities) by D.Khmelev
(http://www.math.toronto.edu/dkhmelev/PROGS/tacu/suffsort-eng.html)
or by sary program.
Example of use:
  suffsort FILE       # produces suffix array in FILE.ary
  maxlcp -q FILE      # outputs 3 numbers
The program outputs three numbers l,m,n: the length of longest repeated
substring, and beginning positions (1-based) of two repetitions of this
substring.
Using this three numbers you can output repeated fragment of the FILE
by command 
  tail -c+<m> FILE|head -c<l>
(substitute numerical values instead of <m> and <l>). You can verify
that the outputted fragment is indeed repeated by command
  tail -c+<n> FILE|head -c<l>
(notice <n> instead of <m>).

Also, maxlcp outputs the record values to stderr (this can be
suppressed with -q option).

5  Развитие программы

2003-08-20

2003-08-23

2003-08-24

2004-05-31

6  Лицензия

Программа доступна с http://www.math.toronto.edu/dkhmelev/PROGS/

Автор:

Дмитрий Викторович Хмелёв dkhmelev((at))math.toronto.edu [замените ((at)) на @, чтобы получить настоящий адрес - антиспам]

119 992, Москва, Ленинские горы, МГУ, 1 Гум. корп., Филологический факультет, Лаборатория общей и компьютерной лексикологии и лексикографии.

УСЛОВИЯ ИСПОЛЬЗОВАНИЯ

Эта программа может свободно распространяться на условиях лицензии GNU версии два или выше (см. прилагаемый файл COPYING с условиями распространения).

Результаты, полученные с использованием этой программы должны ссылаться на её использование. Пример ссылки:

Д.В. Хмелёв http://www.math.toronto.edu/dkhmelev/PROGS/

Более того, Вы должны проинформировать автора о публикации.

Используя эту программу Вы соглашаетесь с условиями использования.

ОТСУТСТВИЕ ГАРАНТИЙНЫХ ОБЯЗАТЕЛЬСТВ

ПОСКОЛЬКУ НАСТОЯЩАЯ ПРОГРАММА РАСПРОСТРАНЯЕТСЯ БЕСПЛАТНО, ГАРАНТИИ НА НЕЕ НЕ ПРЕДОСТАВЛЯЮТСЯ В ТОЙ СТЕПЕНИ, В КАКОЙ ЭТО ДОПУСКАЕТСЯ ПРИМЕНИМЫМ ПРАВОМ. НАСТОЯЩАЯ ПРОГРАММА ПОСТАВЛЯЕТСЯ НА УСЛОВИЯХ "КАК ЕСТЬ". ЕСЛИ ИНОЕ НЕ УКАЗАНО В ПИСЬМЕННОЙ ФОРМЕ, АВТОР И/ИЛИ ИНОЙ ПРАВООБЛАДАТЕЛЬ НЕ ПРИНИМАЕТ НА СЕБЯ НИКАКИХ ГАРАНТИЙНЫХ ОБЯЗАТЕЛЬСТВ, КАК ЯВНО ВЫРАЖЕННЫХ, ТАК И ПОДРАЗУМЕВАЕМЫХ, В ОТНОШЕНИИ ПРОГРАММЫ, В ТОМ ЧИСЛЕ ПОДРАЗУМЕВАЕМУЮ ГАРАНТИЮ ТОВАРНОГО СОСТОЯНИЯ ПРИ ПРОДАЖЕ И ПРИГОДНОСТИ ДЛЯ ИСПОЛЬЗОВАНИЯ В КОНКРЕТНЫХ ЦЕЛЯХ, А ТАКЖЕ ЛЮБЫЕ ИНЫЕ ГАРАНТИИ. ВСЕ РИСКИ, СВЯЗАННЫЕ С КАЧЕСТВОМ И ПРОИЗВОДИТЕЛЬНОСТЬЮ ПРОГРАММЫ, НЕСЕТ ЛИЦЕНЗИАТ. В СЛУЧАЕ ЕСЛИ В ПРОГРАММЕ БУДУТ ОБНАРУЖЕНЫ НЕДОСТАТКИ, ВСЕ РАСХОДЫ, СВЯЗАННЫЕ С ТЕХНИЧЕСКИМ ОБСЛУЖИВАНИЕМ, РЕМОНТОМ ИЛИ ИСПРАВЛЕНИЕМ ПРОГРАММЫ, НЕСЕТ ЛИЦЕНЗИАТ.

ЕСЛИ ИНОЕ НЕ ПРЕДУСМОТРЕНО ПРИМЕНЯЕМЫМ ПРАВОМ ИЛИ НЕ СОГЛАСОВАНО СТОРОНАМИ В ДОГОВОРЕ В ПИСЬМЕННОЙ ФОРМЕ, АВТОР И/ИЛИ ИНОЙ ПРАВООБЛАДАТЕЛЬ, КОТОРЫЙ МОДИФИЦИРУЕТ И/ИЛИ РАСПРОСТРАНЯЕТ ПРОГРАММУ НА УСЛОВИЯХ НАСТОЯЩЕЙ ЛИЦЕНЗИИ, НЕ НЕСЕТ ОТВЕТСТВЕННОСТИ ПЕРЕД ЛИЦЕНЗИАТОМ ЗА УБЫТКИ, ВКЛЮЧАЯ ОБЩИЕ, РЕАЛЬНЫЕ, ПРЕДВИДИМЫЕ И КОСВЕННЫЕ УБЫТКИ (В ТОМ ЧИСЛЕ УТРАТУ ИЛИ ИСКАЖЕНИЕ ИНФОРМАЦИИ, УБЫТКИ, ПОНЕСЕННЫЕ ЛИЦЕНЗИАТОМ ИЛИ ТРЕТЬИМИ ЛИЦАМИ, НЕВОЗМОЖНОСТЬ РАБОТЫ ПРОГРАММЫ С ЛЮБОЙ ДРУГОЙ ПРОГРАММОЙ И ИНЫЕ УБЫТКИ). АВТОР И/ИЛИ ИНОЙ ПРАВООБЛАДАТЕЛЬ В СООТВЕТСТВИИ С НАСТОЯЩИМ ПУНКТОМ НЕ НЕСУТ ОТВЕТСТВЕННОСТИ ДАЖЕ В ТОМ СЛУЧАЕ, ОНИ БЫЛИ ПРЕДУПРЕЖДЕНЫ О ВОЗМОЖНОСТИ ВОЗНИКНОВЕНИЯ ТАКИХ УБЫТКОВ.