Программа lcp версия 0.1.9

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

1  Загрузка

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

2  Файл readme.koi

lcp --- построение индекса LCP из суффиксного массива


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

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


КОМПИЛЯЦИЯ

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


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

См. помощь к программе:
  lcp --help


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

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

user@computer$ ./lcp --help
USAGE: lcp [OPTIONS] FILE 
INPUT files: FILE  FILE.ary
OUTPUT: FILE.lcp with information on common prefixes
Mandatory arguments to long options are mandatory for short options too.
GENERAL OPTIONS:
  -a, --suffix-array=<name>  take suffix array for FILE from <name>
  -o, --lcp-array=<lcpname>        output lcp array to file <name>
LCP RECONSTRUCTION ALGORITHM
  -k, --Kasai-Lee-alg     Kasai-Lee (cf [1] in `lcp -m`)
  -r<num>, or             resilience(use optional parameter
  --resilience-alg <num>  <num=1> to decrease memory use)
  -s, --synthesis-alg     (default) synthesis
  -n, --naive-alg         naive
OUTPUT OPTIONS
  -t, --stdout            output result to stdout
  -d, --digital           print lcp's as digital numbers separated by newline
  -c, --clocks            output clocks of the program (depends on algorithm)
  -i, --information       output in three lines (max. lcp, sum of lcp, avg.lcp)
INFORMATION
  -q, --quiet             stop messages to stderr and shorten other messages
  -h, --help              display this help and exit
  -m, --man               display complete description
  -v, --version           display version and exit

4  Описание

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


DESCRIPTION

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
  lcp FILE            # produces FILE.lcp from FILE.ary
Suppose that length(FILE)=size. Denote suffix array by SA[0..size-1].
The lcp[0..size-2] array is defined by relation 
  lcp[i]=LCP(FILE[SA[i]..size-1],FILE[SA[i+1]..size-1])
This program realizes four algorithms for lcp[] construction from the
suffix array, which can be selected by switches:

Naive algorithm (-n --naive-alg)
Straightforward computing with potential O(size*size) time complexity.
Consumed memory: (12+1)*size bytes

Kasai-Lee algorithm (-k --Kasai-Lee-alg)
Linear time lcp reconstruction algorithm described in [1].
Consumed memory: (12+1)*size bytes

Resilience algorithm (-r --resilience-alg)
Algorithm by D.Khmelev, based on *resilience* property of suffix arrays
Consumed memory: (8+1)*size bytes. If optional factor <num> is specified
e.g.
 lcp -r 4 FILE 
then the memory consumption became (1+(8/num))*size bytes ((1+8/4)*size or
3*size above). These comes in trade-off with increasing computation time
by factor <num> for highly repetitive files.

Synthesis algorithm (-s --synthesis-alg, default)
The mixture of naive and resilience algorithm. Time behaviour is O(size),
while space consumption is (1+8/64)*size or 1.125*size.

[1] T. Kasai, G.Lee et al. Linear-Time Longest-Common-Prefix Computation
in Suffix Arrays and Its Applications//CPM 2001, LNCS 2089, pp.181--192,
Springer-Verlag Berlin Heidelberg, 2001

DATA REPRESENTATION

We assume that the suffix array SA[0..size-1] of unsigned integers 0..2^32-1
for character array FILE[0..size-1] is kept in FILE.ary in big-endian
format. Array lcp[0..size-2] of unsigned integers 0..2^{32}-1 is outputted to
FILE.lcp in 4-byte big endian format either.
To read an integer from this file use the following macros in C:

// The next definition should be used for reading from binary file "rb"
static unsigned char __cint[4];//REQUIRED SIZEOFINT==4!!!!
#define GETINT(f,fname) (fread(&__cint,1,SIZEOFINT,f)==4?\
  (256*(256*(256*__cint[0]+__cint[1])+__cint[2])+__cint[3]):\
  (fprintf(stderr,"Failed to read big-endian 4-byte integer from %s\n",fname),\
   exit(1),0))

To write an integer in big-endian format we used the following procedure:

void write_bigendian_unsigned_int_to_file(FILE *fp, unsigned int n)
{
  fputc((n & 0xFF000000) >> 24, fp);
  fputc((n & 0xFF0000) >> 16, fp);
  fputc((n & 0xFF00) >> 8, fp);
  fputc((n & 0xFF), fp);
}

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

2003-08-23

2003-08-24

2003-08-26

2003-08-27

2003-08-28

2003-08-29

2003-09-13

2003-09-14

2003-09-19

2004-01-19

2004-04-10

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/

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

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

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

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

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