Алгоритмы сжатия в определении авторства Д.В.Хмелёв Translate this page into: Эта работа посвящена использованию алгоритмов сжатия данных в задаче определения авторства, а также приведем результаты проверки этого нового метода на примере той же выборки данных, что использовалась в в работе [1]. Вначале нам потребуется несколько определений, которые, впрочем, не должны испугать математически неподготовленного читателя в силу своей простоты. Под текстом здесь понимается последовательность букв из некоторого алфавита A. Длину текста B мы опять будем обозначать через |B|. Назовем конкатенацией текстов B и A последовательность S длины |B|+|A|, начало которой совпадает с B, а конец совпадает с A. При этом будем писать, что S = A.B. Дадим теперь <<идеальное>> определение относительной сложности в духе определения колмогоровской сложности (по поводу которой см. [2], а также оригинальную работу А.Н. Колмогорова [3]): относительная сложность K(A | B) текста A относительно текста B - это длина наименьшей программы в двоичном алфавите, которая переводит текст B в текст A. К сожалению, K(A | B) невычислима и неясно как можно ее использовать на практике. Некоторое грубое приближение к ней, впрочем, вполне достаточное, как мы увидим далее, для целей определения авторства, можно получить с помощью алгоритмов сжатия данных. Определим относительную сложность C(A | B) текста A по отношению к тексту B следующим образом. Сожмем текст B в текст B', и текст S = B.A в текст S'. Теперь положим C(A | B) = |S'|-|B'|. Данное определение содержит неоднозначность, ибо не сказано, каким именно способом производится сжатие. В настоящем исследовании будет использоваться несколько способов сжатия, которые описаны ниже. Нас интересует применение функции C(A | B) в задаче определения авторства. Предположим, что у нас имеются тексты n авторов. Отберем у каждого автора по контрольному тексту U1, ..., Un. Все остальные тексты у каждого автора объединим в один текст T1, ..., Tn. Для каждого контрольного текста i авторство определяется следующим образом. Сначала определяется ранг Ri числа C(Ui | Ti) в наборе чисел {C(Ui | T1), ..., C(Ui | Tn)}. Ранги принимают значения от 0 до n-1. Если ранг Ri равен 0, то авторство i-того контрольного текста определено верно. Аналогично [1] можно ввести много различных характеристик точности метода определения авторства. Например, 1) Простейшая характеристика - число нулевых рангов Ri 2) Более обобщенную характеристику дает средний ранг M = 1 n nе i = 1 Ri. Проверка различных алгоритмов сжатия проведена на корпусе текстов, который использовался в [1]. Как упомянуто ранее, корпус состоит из 385 текстов 82 писателей. Общий объем текстов составляет около 128 миллионов букв. Тексты подверглись предварительной обработке. Во-первых, были склеены все слова, разделенные переносом. Далее были выкинуты все слова, начинавшиеся с прописной буквы. Оставшиеся слова помещены в том порядке, в котором они находились в исходном файле с разделителем из символа перевода строки. У каждого из n писателей было отобрано по контрольному произведению Ui. Остальные тексты были слиты в обучающие тексты Ti, i = 1, ..., 82. Объем каждого контрольного произведения составлял не менее 50-100 тысяч букв. Рассмотрим теперь возможные алгоритмы сжатия данных без потерь. Следующие алгоритмы наиболее популярны в последнее время: кодирование Хаффмана, арифметическое кодирование, метод Барроуза-Виллера [4] и множество вариаций метода Лемпеля-Зива [5]. Некоторые алгоритмы специально ориентированы на сжатие текста: это алгоритмы PPM [6] (использующие марковскую модель небольшого порядка) и DMC (использующий динамически изменяемую марковскую модель) [7]. Каждый алгоритм имеет большое число модификаций и параметров (например, существует динамическое кодирование Хаффмана, далее, варьируется объем используемого словаря и пр. и пр.). Кроме того, существует множество <<смешанных>> алгоритмов, где текст, сжатый, например, с помощью алгоритма PPM, дополнительно кодируется с помощью кода Хаффмана. Все эти алгоритмы реализованы в многочисленных программах, которых в настоящий момент существует не менее 150. Каждая из них реализует, вообще говоря, разные варианты алгоритмов сжатия данных. Дополнительное разнообразие возникает из-за того, что у многих программ имеется несколько версий, которые также имеют разные алгоритмы сжатия. Было отобрано лишь несколько из них, широко представляющих весь спектр программ сжатия данных, которые и показаны в табл. 1. Table 1: Программы сжатия ПрограммаАвтор [Используемые || алгоритмы] 1. 7zip версия 2.11Игорь Павлов арифм. кодирование, LZ + арифметическое кодирование, PPM 2. arj версия 2.60 RAO Inc. LZSS + Хаффман 3. bsa версия 1.9.3 Сергей Бабичев LZ 4. bzip2 Джулиан СьюардБарроуз-Виллер + Хаффман 5. compress Sun Inc. LZW 6. dmc Гордон В. КормакDMC 7. gzip Жан-Луи Гаиликод Шеннона-Фано, Хаффман 8. ha версия 0.999cГарри Хирвола Скользящее окно словаря + арифм. 9. huff1 Вильям Демас (LDS 1.1) статический Хаффман 10. lzari Харахико Окумура (LDS 1.1) LZSS+арифм. 11. lzss Харахико Окумура (LDS 1.1) LZSS 12. ppm Вильям ТеаханPPM 13. ppmd5 версия FДмитрий ШкаринPPM 14. rar версия 2.00Евгений Рошаль вариант LZ77 + Хаффман 15. rar версия 2.70Евгений Рошаль вариант LZ77 + Хаффман 16. rk версия 1.03a Малькольм Тейлор LZ, PPMZ Большинство из этих программ с описаниями можно получить из Индекса архиваторов1, который поддерживает Джефф Гилхрист2. Программа compress взята из операционной системы SunOS 5.6. Программа dmc доступна по ftp3. Заметим, что dmc имеет опцию максимума используемой оперативной памяти. В нашем случае использовалась опция в 100000000 байт. Пакет программ LDS 1.1 также доступен по ftp4. Программа ppm доступна с домашней страницы её автора5. Результаты применения этих программ представлены в табл. 2, где в последней строке приведены данные, которые получаются при применении цепей Маркова (см. [1]). на том же материале. Вычисления, выполненные при составлении табл. 2, проводились под несколькими операционными системами на разных платформах и заняли около трех недель непрерывного счета. Table 2: Точность определения авторства текста с использованием алгоритмов сжатия данных ПрограммаРанг 01234 і 5M 7zip399323266.43 arj465272205.16 bsa449311245.30 bzip2385513313.68 compress1211326324.37 dmc364344319.81 gzip504121244.55 ha478133205.60 huff110114425115.37 lzari1754264814.99 lzss1431136020.05 ppm22142134010.39 ppmd546662225.96 rar 2.7058111217.22 rar 2.007132151.44 rk52931174.20 Цепи Маркова (см. [1])69 3 2 1 7 2.35 Из данных таблицы 2 следует, что программы сжатия угадывают истинных писателей весьма часто. Поэтому их использование, несомненно, имеет смысл. Заметим, что результаты применения программы rar 2.00 даже превосходят результаты, полученные ранее при использовании цепей Маркова. Хотя такое превосходство можно отнести на счет определенной статистической погрешности, этот результат является лучшим на нынешний день. По-видимому, такие прекрасные результаты связаны с тем, что программы сжатия действительно лучше адаптируются к контрольному тексту, переработав к тому времени обучающий текст истинного автора, чем какого-либо другого. Недостатком этого метода по сравнению с методом цепей Маркова [1] является то, что сами алгоритмы сжатия менее <<прозрачны>>, а у коммерческих программ и вовсе недоступны для изучения. Тем не менее, многие среди представленных в табл. 1 программ, например, программы gzip и bzip имеют открытый исходный код и хорошо документированные открытые алгоритмы и дальнейшее их изучение может открыть причины эффективности изложенного подхода к определению авторства. Несомненное достоинство представленного здесь метода определения авторства состоит в том, что он доступен буквально на каждом компьютере и не требует никаких специальных программ при выборе из небольшого числа авторов, поскольку большинство из описанных архиваторов широко распространены, а некоторые (вроде gzip или rar) имеют реализации на всех платформах и всех операционных системах. По поводу объяснения эффективности этого подхода выдвигается гипотеза о том, что данный метод очень эффективно измеряет сложность текста относительны словаря, который используется автором. Заметим, однако, что с нашей точки зрения эта гипотеза всё еще не является вполне удовлетворительной. References [1] Хмелёв Д.В. Распознавание автора текста с использованием цепей А.А. Маркова//Вестн. МГУ. Сер. 9, Филология. 2000. N2. с.115-126. [2] Li M. Vitányi P. An Introduction to Kolmogorov Complexity and Its Applications. Springer, New York, 2nd edition, 1997. [3] Колмогоров А.Н. Три подхода к определению понятия <<количество информации>>//Проблемы передачи информации, т.1, N1, с.3-11, 1965. [4] Burrows M. Wheeler D.J. A block-sorting lossless data compression algorithm//Digital SRC Research Report 124 1994. ftp://ftp.digital.com/pub/DEC/SRC/research-reports/SRC-124.ps.gz [5] Lempel A., Ziv J. On the complexity of finite sequences//IEEE Transactions on Information Theory. 1976. V.22 N1. P.75-81. [6] Cleary J.G., Witten I.H. Data compression using adaptive coding and partial string matching//IEEE Transactions on Communications. 1984. V.32. N4. P.396-402. [7] Cormack G.V. and Horspool R.N . Data Compression Using Dynamic Markov Modelling//The Computer Journal. 1987. V.30. N6. P.541-550. Footnotes: 1 http://web.act.by.net/~act/act-index.html 2 Jeff Gilchrist, jeffg@cips.ca 3 http://plg.uwaterloo.ca/~ftp/dmc/ 4 ftp://garbo.uwasa.fi/pc/programming/lds_11.zip 5 http://www.cs.waikato.ac.nz/~wjt/ File translated from TEX by TTH, version 2.70.On 15 Oct 2001, 15:02.
Эта работа посвящена использованию алгоритмов сжатия данных в задаче определения авторства, а также приведем результаты проверки этого нового метода на примере той же выборки данных, что использовалась в в работе [1].
Вначале нам потребуется несколько определений, которые, впрочем, не должны испугать математически неподготовленного читателя в силу своей простоты. Под текстом здесь понимается последовательность букв из некоторого алфавита A. Длину текста B мы опять будем обозначать через |B|. Назовем конкатенацией текстов B и A последовательность S длины |B|+|A|, начало которой совпадает с B, а конец совпадает с A. При этом будем писать, что S = A.B.
Дадим теперь <<идеальное>> определение относительной сложности в духе определения колмогоровской сложности (по поводу которой см. [2], а также оригинальную работу А.Н. Колмогорова [3]): относительная сложность K(A | B) текста A относительно текста B - это длина наименьшей программы в двоичном алфавите, которая переводит текст B в текст A. К сожалению, K(A | B) невычислима и неясно как можно ее использовать на практике.
Некоторое грубое приближение к ней, впрочем, вполне достаточное, как мы увидим далее, для целей определения авторства, можно получить с помощью алгоритмов сжатия данных. Определим относительную сложность C(A | B) текста A по отношению к тексту B следующим образом. Сожмем текст B в текст B', и текст S = B.A в текст S'. Теперь положим C(A | B) = |S'|-|B'|. Данное определение содержит неоднозначность, ибо не сказано, каким именно способом производится сжатие. В настоящем исследовании будет использоваться несколько способов сжатия, которые описаны ниже.
Нас интересует применение функции C(A | B) в задаче определения авторства. Предположим, что у нас имеются тексты n авторов. Отберем у каждого автора по контрольному тексту U1, ..., Un. Все остальные тексты у каждого автора объединим в один текст T1, ..., Tn.
Для каждого контрольного текста i авторство определяется следующим образом. Сначала определяется ранг Ri числа C(Ui | Ti) в наборе чисел {C(Ui | T1), ..., C(Ui | Tn)}. Ранги принимают значения от 0 до n-1. Если ранг Ri равен 0, то авторство i-того контрольного текста определено верно. Аналогично [1] можно ввести много различных характеристик точности метода определения авторства. Например,
1) Простейшая характеристика - число нулевых рангов Ri
2) Более обобщенную характеристику дает средний ранг
Проверка различных алгоритмов сжатия проведена на корпусе текстов, который использовался в [1]. Как упомянуто ранее, корпус состоит из 385 текстов 82 писателей. Общий объем текстов составляет около 128 миллионов букв. Тексты подверглись предварительной обработке. Во-первых, были склеены все слова, разделенные переносом. Далее были выкинуты все слова, начинавшиеся с прописной буквы. Оставшиеся слова помещены в том порядке, в котором они находились в исходном файле с разделителем из символа перевода строки. У каждого из n писателей было отобрано по контрольному произведению Ui. Остальные тексты были слиты в обучающие тексты Ti, i = 1, ..., 82. Объем каждого контрольного произведения составлял не менее 50-100 тысяч букв.
Рассмотрим теперь возможные алгоритмы сжатия данных без потерь. Следующие алгоритмы наиболее популярны в последнее время: кодирование Хаффмана, арифметическое кодирование, метод Барроуза-Виллера [4] и множество вариаций метода Лемпеля-Зива [5]. Некоторые алгоритмы специально ориентированы на сжатие текста: это алгоритмы PPM [6] (использующие марковскую модель небольшого порядка) и DMC (использующий динамически изменяемую марковскую модель) [7]. Каждый алгоритм имеет большое число модификаций и параметров (например, существует динамическое кодирование Хаффмана, далее, варьируется объем используемого словаря и пр. и пр.). Кроме того, существует множество <<смешанных>> алгоритмов, где текст, сжатый, например, с помощью алгоритма PPM, дополнительно кодируется с помощью кода Хаффмана.
Все эти алгоритмы реализованы в многочисленных программах, которых в настоящий момент существует не менее 150. Каждая из них реализует, вообще говоря, разные варианты алгоритмов сжатия данных. Дополнительное разнообразие возникает из-за того, что у многих программ имеется несколько версий, которые также имеют разные алгоритмы сжатия. Было отобрано лишь несколько из них, широко представляющих весь спектр программ сжатия данных, которые и показаны в табл. 1.
Большинство из этих программ с описаниями можно получить из Индекса архиваторов1, который поддерживает Джефф Гилхрист2. Программа compress взята из операционной системы SunOS 5.6. Программа dmc доступна по ftp3. Заметим, что dmc имеет опцию максимума используемой оперативной памяти. В нашем случае использовалась опция в 100000000 байт. Пакет программ LDS 1.1 также доступен по ftp4. Программа ppm доступна с домашней страницы её автора5.
Результаты применения этих программ представлены в табл. 2, где в последней строке приведены данные, которые получаются при применении цепей Маркова (см. [1]). на том же материале. Вычисления, выполненные при составлении табл. 2, проводились под несколькими операционными системами на разных платформах и заняли около трех недель непрерывного счета.
Из данных таблицы 2 следует, что программы сжатия угадывают истинных писателей весьма часто. Поэтому их использование, несомненно, имеет смысл. Заметим, что результаты применения программы rar 2.00 даже превосходят результаты, полученные ранее при использовании цепей Маркова. Хотя такое превосходство можно отнести на счет определенной статистической погрешности, этот результат является лучшим на нынешний день.
По-видимому, такие прекрасные результаты связаны с тем, что программы сжатия действительно лучше адаптируются к контрольному тексту, переработав к тому времени обучающий текст истинного автора, чем какого-либо другого. Недостатком этого метода по сравнению с методом цепей Маркова [1] является то, что сами алгоритмы сжатия менее <<прозрачны>>, а у коммерческих программ и вовсе недоступны для изучения. Тем не менее, многие среди представленных в табл. 1 программ, например, программы gzip и bzip имеют открытый исходный код и хорошо документированные открытые алгоритмы и дальнейшее их изучение может открыть причины эффективности изложенного подхода к определению авторства.
Несомненное достоинство представленного здесь метода определения авторства состоит в том, что он доступен буквально на каждом компьютере и не требует никаких специальных программ при выборе из небольшого числа авторов, поскольку большинство из описанных архиваторов широко распространены, а некоторые (вроде gzip или rar) имеют реализации на всех платформах и всех операционных системах.
По поводу объяснения эффективности этого подхода выдвигается гипотеза о том, что данный метод очень эффективно измеряет сложность текста относительны словаря, который используется автором. Заметим, однако, что с нашей точки зрения эта гипотеза всё еще не является вполне удовлетворительной.
1 http://web.act.by.net/~act/act-index.html
2 Jeff Gilchrist, jeffg@cips.ca
3 http://plg.uwaterloo.ca/~ftp/dmc/
4 ftp://garbo.uwasa.fi/pc/programming/lds_11.zip
5 http://www.cs.waikato.ac.nz/~wjt/