Текстовый анализатор: распознавание авторства (окончание)

    Эта статья об алгоритме распознавания авторства, реализованном в проекте «Текстовый анализатор». В окончании статьи мы рассмотрим, как собираются частотные характеристики, и в общих чертах познакомимся с нейросистемой Хэмминга. (Начало и продолжение).

    Структура статьи:
    1. Анализ авторства
    2. Знакомство с кодом
    3. Внутренности TAuthoringAnalyser и хранение текстов
    4. Разбиение на уровни конечным автоматом на стратегиях
    5. Сбор частотных характеристик
    6. Нейросеть Хэмминга и анализ авторства

    Дополнительные материалы:
    • Исходники проекта «Текстовый анализатор» (Borland C++ Builder 6.0)
    • Тестирование нейросистемы Хэмминга в Excel'е ([xls])
    • Таблица переходов для КА, разбивающего текст на уровни ([xls])
    • Расчет благозвучия отдельных букв ([xls])
    • Презентация дипломного проекта «Текстовый анализатор» ([ppt])
    • Презентация проекта «Карта благозвучия» ([ppt])
    • Все эти материалы в сжатом виде ([zip], [7z], [rar])




    5. Сбор частотных характеристик



    Наиболее полезны для распознавания авторства частотные характеристики отдельных символов, двух-, трёхбуквенных сочетаний, частотные таблицы слов и т.д. В этой программе реализовано только самое простое: подсчет частот символов. Конечно, для комплексного анализа этого недостаточно. Сейчас точность распознавания, надо признать, не очень высокая. Насколько помню, в тестах вероятность правильного ответа достигала 60-70 процентов, и то — в идеальных условиях. Разрабатывая программу, я надеялся когда-нибудь её переписать, добавив комплексный анализ авторства на основе многих методов. Кто знает, может, ещё и возьмусь…

    Итак, сбор частотных характеристик символов. Класс TCharFrequencyCalculator ([h]) составляет частотную таблицу, выполняя один проход по тексту. Шаблонный класс TFrequencyTable ([h]) может хранить частотную таблицу для объектов любого типа.

    Copy Source | Copy HTML
    1. class TCharFrequencyCalculator
    2. {
    3. private:
    4.  
    5.     TFrequencyTable<TChar> _FTable;
    6.  
    7. public:
    8.  
    9.     TFrequencyTable<TChar> & operator ()(TTextStringWrapper & tWrapper)
    10.     {
    11.         _FTable << ftm_Clear;
    12.  
    13.     TUInt i;
    14.         TTextStringWrapper d; // Эта переменная, видимо, просто мусор в коде...
    15.         for (i=tWrapper.Begin(); i<=tWrapper.End(); i++)
    16.             _FTable << (tWrapper[i]);
    17.     return _FTable;
    18.     };
    19.  
    20.     TFrequencyTable<TChar> & operator ()(const TTextString & tTextString)
    21.     {
    22.         _FTable << ftm_Clear;
    23.  
    24.         for (TSInt i=1; i<=tTextString.Length(); i++)
    25.             _FTable << tTextString[i];
    26.     return _FTable;
    27.     };
    28.  
    29.     TCharFrequencyCalculator(){};
    30. };


    // Использование:
    TCharFrequencyCalculator calculator;
    TFrequencyTable charFrequencyTable = calculator(text);


    Стоит обратить внимание на то, что функций, подсчитывающих частоты, аж две. Первая принимает TTextStringWrapper ([cpp], [h]) — класс-обёртку над текстовой строкой. «Обёртка» ещё известна как паттерн Адаптер (Adapter, Wrapper, [1], [2], [3]). Он преобразует интерфейс одного класса в интерфейс другого. Можно было сделать по-настоящему универсальный калькулятор, но пришлось бы абстрагироваться от объектов, частоты которых мы подсчитываем. Калькулятора вообще не должно волновать, в каких списках, таблицах или массивах там хранятся данные, откуда берутся, сколько элементов, и в каком они порядке. Адаптированные под нужный калькулятору интерфейс, списки объектов обрабатывались бы единообразно… У вас не возникло ощущения дежа-вю? Правильно, мы это уже обсуждали, когда рассматривали менеджер конечного автомата. Там мы абстрагировались от списков событий с помощью паттерна «Итератор», а здесь — от списков элементов с помощью «Адаптер». Это его нетипичное применение, оно хуже, чем итераторы: нам бы пришлось наплодить иерархии адаптеров и частотных таблиц, чтобы их можно было оперативно заменять. В конце концов, адаптер перестал бы быть собой, а превратился в некий абстрактный контейнер. Примерно так бы это выглядело:

    Copy Source | Copy HTML
    1. class TFrequencyCalculator
    2. {
    3.     TFrequencyTable * operator ()(TWrapper * tWrapper, TFrequencyTable *table)
    4.     {
    5.         table << ftm_Clear;
    6.  
    7.         for (int i=tWrapper->Begin(); i<=tWrapper->End(); ++i)
    8.             table << (tWrapper->at(i));
    9.     return table;
    10.     };
    11. }
    12.  
    13. class TWordWrapper : public TWrapper
    14. {
    15. // ......
    16.     virtual int Begin() const;
    17.     virtual int End() const;
    18.     virtual Word at(const int &index) const;
    19. // ......
    20. };
    21.  
    22. class TSentenceWrapper : public TWrapper {/*......*/};
    23. class TWordsFrequencyTable : public TFrequencyTable {/*......*/};
    24. class TSentenceFrequencyTable : public TFrequencyTable {/*......*/};
    25.  
    26. // Использование:
    27. TWordWrapper wordWrapper = TWordWrapper(wordsList)
    28. TFrequencyCalculator wordCalc;
    29. TWordsFrequencyTable wordFrequencyTable = wordCalc(&wordWrapper, &wordFrequencyTable);
    30.  
    31. TSentenceWrapper sentenceWrapper = TSentenceWrapper(sentencesMap)
    32. TFrequencyCalculator sentenceCalc;
    33. TSentenceFrequencyTable sentenceFrequencyTable = sentenceCalc(&sentenceWrapper, &sentenceFrequencyTable);
    34.  


    6. Нейросеть Хэмминга и анализ авторства



    Наконец, мы с вами, уставшие и побитые, добрались до самого последнего шага. Нейросеть Хэмминга ([1], [2]) берёт за основу набор бинарных векторов одинаковой длины. Они называются образцами и хранятся в матрице образцов. На вход нейросети подаётся тестируемый вектор той же длины. Количество входов равно размеру вектора; для данных большого объёма входов может быть очень много. Одно из преимуществ ИНС Хэмминга (перед ИНС Хопфилда) в том, что какой бы ни была размерность входного вектора, структура нейросети не поменяется. Слоёв — два, причём первый фиктивный; выходов и нейронов в каждом слое ровно столько, сколько образцов в матрице. Нейросеть работает быстро. Её задача — найти в матрице образцов вектор, который больше всего «похож» на входной. Похожесть определяется так называемым расстоянием Хэмминга. Чем меньше это расстояние, тем более «похожи» два вектора. Условно говоря, расстояние Хэмминга показывает, сколько битов в этих векторах не совпадает. Посчитать расстояние Хэмминга несложно, да и вся нейросеть — это лишь удобное представление нескольких простых формул. Вычислив какие-то значения, нейросеть сходится к результату: на выходах будет получен вектор со всеми нуликами, — исключая какой-нибудь один выход, где появится единица. Индекс этого выхода указывает на искомый образец в матрице образцов.

    Чтобы загрузить в нейросеть (класс THamNeuroSystem: [cpp], [h]) образцы текстов, их нужно преобразовать к бинарному виду. Это делает шаблонный класс-коннектор (THamNSConnector: [h]). Забавно видеть код нейросети и коннектора: я понимаю, что это можно сделать гораздо, гораздо проще.

    Copy Source | Copy HTML
    1. template <class T> void THamNSConnector<T>::ByteToBinaryVector(T DataItem, TSInt SizeOfData, TSampleVector *DestinationVector)
    2. {
    3. vector <bool> BoolBits;
    4. T NewDataItem = DataItem;
    5.  
    6.     for (TSInt i=1; i<SizeOfData; i++)
    7.     {
    8.         BoolBits.clear();
    9.  
    10.         BoolBits.push_back( NewDataItem & bitOne );
    11.         BoolBits.push_back( NewDataItem & bitTwo );
    12.         BoolBits.push_back( NewDataItem & bitThree );
    13.         BoolBits.push_back( NewDataItem & bitFour );
    14.         BoolBits.push_back( NewDataItem & bitFive );
    15.         BoolBits.push_back( NewDataItem & bitSix );
    16.         BoolBits.push_back( NewDataItem & bitSeven );
    17.         BoolBits.push_back( NewDataItem & bitEight );
    18.  
    19.         for (TUInt j= 0; j<BoolBits.size(); j++)
    20.                 {
    21.             if (BoolBits[j]) DestinationVector->push_back(1);
    22.             else DestinationVector->push_back( 0);
    23.                 }
    24.  
    25.     NewDataItem = NewDataItem >> 8;
    26.     };
    27. };
    28.  
    29. template <class T> TSampleVector THamNSConnector<T>::VectorToBinaryVector(TVector SourceVector)
    30. {
    31.     TSInt SizeOfData;
    32.     T DataItem;
    33.     TUInt i;
    34.     TSampleVector ResVector;
    35.  
    36.     SizeOfData = sizeof(T);
    37.  
    38.     for (i= 0; i<SourceVector.size(); i++)
    39.     {
    40.         DataItem = SourceVector[i];
    41.         ByteToBinaryVector(DataItem, SizeOfData, &ResVector);
    42.     };
    43.  
    44.     return ResVector;
    45. };
    46.  


    На этом всё. Если не считать моих попыток улучшить нейросеть, больше рассказывать не о чем. Нейросеть возвращает индекс образца того текста, характеристики которого она считает более сходными с характеристиками текста неизвестного автора. Насколько правдив ответ, вы можете выяснить сами, скомпилировав программу. Меня на обширные тесты не хватило ни тогда, при написании диплома, ни сейчас. Надеюсь, статья была полезна.

    С уважением.

    Комментарии 18

    • НЛО прилетело и опубликовало эту надпись здесь
        +2
        Намекаете, что это не моё? Это моё. От корки и до корки.
        +3
        Вот бы через такой анализатор пропустить C++ код и узнать авторство.
          0
          Возможно, проще было бы воспользоваться Гуглем. Код в меньшей мере отражает стиль автора, чем текст, поскольку есть очень много стандартов кодирования, систем именования, парадигм. И быдлокод везде похож.
            0
            Пращур этого Гуттенберга некогда изобрёл книгопечатный станок, и вот до чего это довело его потомка! Яблоко от яблоньки.
            0
            У меня немного критический вопрос, но тем не менее релевантный к теме вашей работы:) Чем ваша работа лучше, чем уже существующие разработки в этой области, если вы не выполняли обширных тестов, чтобы сравнивать ваше решение с уже существующими? Полагаю все же, что у вас есть некоторые преимущества, если есть дипломы с конференций.
              0
              Преимущества, без сомнений, есть. Для начала: методы разработаны мною. Сколько ни рыл, нигде не применялась нейросистема. (А карта благозвучия и вовсе моё изобретение.) И хотя для комплексного анализа авторства не хватает, разумеется, теории вероятности, ещё один метод распознавания — это хорошо. Моя программа представляет собой эксперимент, исследование. Для стадии производства она не годится; но значительная ценность программы в том, что начинаешь понимать, как её нужно писать, когда она закончена. То есть, я готов написать с нуля ещё одну или даже две версии, которые, в конце концов, могли бы стать полноценным продуктом. Заметьте ещё, что эта работа значительно выше любой дипломной работы.
                0
                Но это смотря в каком универе вы защищаете диплом, у меня бы в универе вас даже до защиты не допустили бы без сравнения с существующими аналогами и обоснованием чем у вас лучше и не изобретаете ли вы велосипед. :)

                А вообще работы такие с нейросетями уже были и достаточно много scholar.google.com/scholar?hl=en&q=authorship+neural+networks&btnG=Search&as_sdt=0%2C5&as_ylo=&as_vis=0
              0
              А в скомпилированном виде нет программки?
              +3
              Теперь мы наконец-то сможем узнать, действительно ли Шолохов написал Тихий Дон?
                0
                Я на его счёт не сомневался. :)
                +1
                Эффективность не слишком высокая, может, имеет смысл сравнить с предыдущими работами?
                Вопросами авторства занимался еще Колмогоров, неплохую работу написали Фоменко Т. и В. (родители «того самого») www.chronologia.org/xpon2/dop3.html. Первый сервис на русском «Штампомер» teneta.rinet.ru/2000/hudlomer/s.html сделал Делицын.
                Сравните, для начала, с ним, если есть продвижение, имеет смысл идти дальше.
                  0
                  Спасибо за ссылки. «Штампомер» не умеет много гитик больших текстов. И он сравнивает 1 текст с 1. Это жуть как неудобно. Лучше сравнивать с «Лингвоанализатором» (http://www.google.ru/url?sa=t&source=web&cd=1&ved=0CBcQFjAA&url=http%3A%2F%2Fwww.rusf.ru%2Fbooks%2Fanalysis%2F&rct=j&q=%D0%9B%D0%B8%D0%BD%D0%B3%D0%B2%D0%BE%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%82%D0%BE%D1%80&ei=avliTc2pH4mEOqnqrO8N&usg=AFQjCNFq3iaCxxYzYou0_vdoyhR0A165ew&sig2=-OSfhoW7QseIp0z49GU2CA&cad=rja). Могу вас уверить, что если бы в моей программе было больше характеристик текста, она стала бы не менее точной; тем паче, я планировал добавить и другие методы распознавания авторства, не только с помощью нейросистемы, но и, в частности, с помощью теории вероятности. Суть была не в том, чтобы создать инструмент (хотя диплом я так и позиционировал, но это для защиты), суть была в том, чтобы написать экспериментальную программу, основываясь на которой можно написать настоящую, для производства.
                  0
                  На каких авторах\произведениях тестировалась программа?
                    0
                    Добрый день!

                    Вот тестовые наборы:

                    Дэн Браун — Код да Винчи
                    Лукьяненко Перумов — Не время для драконов
                    Перумов — Алмазный меч Деревянный меч
                    Роджер Желязны — Дилвиш Проклятый
                    Роджер Желязны — Хроники Эмбера 1
                    Роджер Желязны — Хроники Эмбера 2
                    Рэй Брэдбери — Лед и пламя 1-6 главы
                    Рэй Брэдбери — Лед и пламя 7-9 главы
                    Сергей Лукьяненко — Ночной дозор
                    Сергей Лукьяненко — Черновик
                    Станислав Лем — Из воспоминаний Ийона Тихого
                    Станислав Лем — Осмотр на месте

                    Александр Дихнов — Один мертвый керторианец
                    Александр Дихнов — Три луны Кертории
                    Альфред Ван-Вогт — Галактика М33
                    Борис Акунин — Азазель
                    Борис Акунин — Смерть Ахиллеса
                    Льюис Кэрролл — Алиса в Зазеркалье
                    Льюис Кэрролл — Алиса в стране чудес
                    Перумов — Гибель Богов
                    Рэй Брэдбери — 451 градус по Фаренгейту
                    Сергей Лукьяненко — Чистовик
                    Супруги Дихновы — Дракон-детектив

                    Если не секрет, с чем связан ваш интерес? Мне любопытно :)

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                  Самое читаемое