Программа cross-entropy версия 1.3.2

Проект начат 2002-08-29; Последние изменения 2003-08-22

1  Загрузка

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

2  Файл readme.koi

cross-entropy --- вычисление относительной энтропии
                  и индекса повторяемости

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

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


КОМПИЛЯЦИЯ 

Чтобы откомпилировать программу, запустите (GNU) make в директории, в
которой находится файл readme.koi

Программа окажется в каталоге ./bin


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

Эту программу можно использовать для вычисления относительной энтропии
одного файла по отношенению к другому. Программа использует суффиксные
массивы, так что максимальные накладные расходы по памяти составляют
учетверённый размер текстов. Однако, время вычисления и объём
требуемой памяти могут быть существенно сокращены, если суффиксные
массивы построены предварительно (например, с помощью программы
suffsort из пакета TACU). Программа использует цепь Маркова заданного
порядка для нахождения оценки на относительную энтропию. Однако,
чем больше порядок модели, тем меньше точность оценки.

Вы можете прочитать об оценке энтропии в статье

Кукушкина О.В., Поликарпов А.А., Хмелёв Д.В. Определение авторства
текста с использованием буквенной и грамматической
информации//Проблемы передачи информации, 2001, т.37, вып.2,
с.96-108. Translated in «Problems of Information Transmission»,
pp. 172-184.
http://www.math.toronto.edu/dkhmelev/PAPERS/published/gramcodes/gramcodeswin.html

Эта программа также может вычислять относительный индекс повторяемости
(R-measure) одного текста относительно другого. Более подробное
описание индекса повторяемости (вкупе с примерами применения программы к
вычислению относительной энтропии) можно найти в следующей статье 

Khmelev D., Teahan W. A repetition based measure for
verification of text collections and for text categorization.
SIGIR'2003, July 28--August 1, 2003, Toronto, Canada.
http://www.math.toronto.edu/dkhmelev/PAPERS/published/2003/sigir/sig.html

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

ОШИБКИ

Версии до 1.2.3 включительно выдавали R()=nan на больших файлах (около
400Кб). Ошибка (заключавшаяся в переполнении типа double) исправлена в
версиях >=1.3.0. 

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

user@computer$ ./bin/cross-entropy --help
Usage: cross-entropy [OPTION]... FILE1 FILE2
  -a, --array               suffix array for FILE1 (default FILE1.ary)
  -b, --barray              suffix array for FILE2 (default FILE2.ary)
  -c, --checkonly           check the correctness of both
                            suffix arrays and exit
  -s, --self-suffix-array   Ignore FILE1.ary and FILE2.ary and calculate
                            suffix arrays itself to do computations
  -o, --order <number>      set the order to be equal to <number> (default 2)
  -l, --low-order <number>  calculate starting from the low order <number> 
  -t, --top-order <number>  to the to <number>
  -r, --repetition-index    calculate R-index
  -q, --quiet               output entropies only
  -h, --help                display this help and exit
  -m, --man                 display description
  -v, --version             display version and exit

4  Описание

user@computer$ ./bin/cross-entropy --man
This program calculates relative entropy of given order(s) of FILE2
w.r.t. FILE1. By default it expects that suffix array for both files
are constructed and are kept in FILE1.ary and FILE2.ary, resp.  If one
of suffix arrays is missed, then cross-entropy tries to construct
suffix array on its own, which increase the computation time
significantly and the memory used by factor 5 (this behaviour may be
forced by --self-suffix-array flag). Suffix arrays are expected in Big
Endians 4-byte per integer format as provided by mksary program by Satoru
Takabayashi.


As a test example one can try to calculate the relative entropy
of file containing the string 'aaaaabaaaaac' only w.r.t. itself.
It's relative entropy is 
  -(8/11 ln(4/5) - 2/11 ln(10)) = 0.5809380541 
The same quantity without normalization is
  2 ln(10) - 8 ln(4/5) = 6.390318596 = 11*0.5809380541,
where ln() is a logarithm w.r.t number e=2.7182818284...

Another example: let test1.txt contains 'aaaaabaaaaac' and test2.txt
contains 'aaaaab'. Then H_2(test2.txt|test1.txt) is 0.639032.

Option -r allows to compute so-called R-index (see description in
papers by Khmelev&Teahan). It applies only when suffix arrays were
precomputed. Examples:
R(test1.txt|test2.txt)=0.679366
R(test2.txt|test1.txt)=1.000000

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

2002-08-29

2002-08-30

2002-09-13

2003-05-16

2003-08-22

6  Лицензия

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

Автор:

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

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

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

Эта программа может использоваться бесплатно в научных исследованиях и в образовательных целях. Для коммерческого использования Вы обязаны получить лицензию у автора.

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

D. Khmelev, Text Analysis and Conversion Utilities http://www.math.toronto.edu/dkhmelev/PROGS/tacu/

Кукушкина О.В., Поликарпов А.А., Хмелёв Д.В. Определение авторства текста с использованием буквенной и грамматической информации//Проблемы передачи информации, 2001, т.37, вып.2, с.96-108. Translated in «Problems of Information Transmission», pp. 172-184. http://www.math.toronto.edu/dkhmelev/PAPERS/published/gramcodes/gramcodeswin.html

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

Эта программа не должна модифицироваться и распространяться без предварительного разрешения автора.

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

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

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

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