Банк Рефератов - Анализ текстов на заимствование методом построения семантических моделей

Рефераты. Анализ текстов на заимствование методом построения семантических моделей

Таким образом, для каждого элемента множества B определяются два подэлемента – текст и уровень заимствования из него текста A:

B = {{ B1, d1}, { B2, d2}, … , { Bn, dn}} (2.1)

Причем, множество B должно быть представлено таким образом, что

(2.2)

Имеет смысл рассматривать не все тексты из множества B, а только те, для которых di < dдоп, где dдоп – допустимый предел заимствований.

Сложность алгоритма поиска расстояния между строками очень зависит от конкретной реализации соответствующего алгоритма. Вывод о том, какой именно из алгоритмов поиска расстояний между строками следует делать исходя из анализа следующих данных:

· Максимальный и средний размеры текстов, которые анализируются на наличие заимствований;

· Максимальный и средний размеры текстов, которые рассматриваются в качестве элементов множества B;

· Величина n;

· Априорная информация о максимальном и среднем d

Наиболее распространенные алгоритмы вычисления размера между строками представлены в таблице 2.1.

Таблица 2.1

Алгоритмы вычисления расстояний между строками

N п/п

Алгоритм

Сложность по времени

Сложность по памяти

Особенности применения

Метод динамического программирования Вагнера и Фишера

O(n, m) = (n+1)*(m+1)

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

Может быть применен для вычисления расстояний подстрок строк A и B за константное время, если было рассчитано расстояние между A и B.

Позволяет, в случае необходимости, получить сами подстроки длиной d за линейное время.

Продолжение таблицы 2.1

Модификация Хиршберга

O(n, m) = n*m

O(n, m) = m+n

Требуется также стековая память для 2*max(n,m)-1 рекурсивных вызовов

Основан на методе Вагнера-Фишера. За счет экономии памяти не позволяет быстро получить общие подстроки длины d.

Алгоритм Ханта-Шиманского

O(n, m) = max2(n,m)*log(max(n,m))

O(n, m) = m*n

Алгоритм будет эффективен для больших по объему данных.

Продолжение таблицы 2.1

Алгоритм Машека и Патерсона

O(n, m) = max(n,m)/log(max(n,m))

O(n, m) = m*n

Единственный алгоритм, для которого оценочное время работы в худшем случае меньше квадратичного. Алгоритм работает очень эффективно на больших объемах данных. Разработчики рекомендуют применять его, когда
m, n > 262418

Алгоритм Уконнена

O(n,m) = d * max(n,m)

O(n, m) = m*n

Метод эффективен, когда расстояние между строками небольшое

Поскольку в задаче анализа текста на заимствование часто приходится иметь дело с базой данных текстов (множество B) очень большого объема, задача оптимизации поиска расстояний по этим текстам является очень актуальной. Для этого имеет смысл перед вычислением расстояний между строками собирать информацию, которая позволит сделать выбор в пользу того или иного алгоритма; эффективным может оказаться метод динамического комбинирования алгоритмов.

Алгоритмы поиска расстояния между строками, как правило, позволяют эффективно применять технологии распределенных и параллельных вычислений.

Метод анализа текстов на заимствование методом анализа релевантностей может оказаться эффективным в том случае, если исходный текст A не изменялся или выполнялись незначительные изменения. Если же выполнялись изменения исходного текста (перевод на другой язык, замена некоторых существительных синонимами), то такой метод может не дать требуемого результата.

2.2. Анализ на базе оценки смысловой нагрузки текста

Данный метод анализа принципиально отличается от того, который был изложен в разделе 2.1, схема организации процесса проверки осуществляется иным способом.

2.2.1. Формирование семантического словаря

Процесс проверки текстов, представленных на естественном языке, на базе алгоритмов анализа смысловой нагрузки опирается на заранее форматизированный банк данных – семантический словарь.

Возможно выделить 2 основных типа словарей, используемых в алгоритмах анализа семантических данных:

1. Базовый словарь.
Данный словарь представляет собой совокупность независимых фактов, уровень достоверности которых является максимальным. В словарь этого уровня предполагается включать:

a. Словарь синонимов;

b. Словарь родственных семантических лексем;

c. Формальные лингвистические правила языков, которые могут быть выражены в виде фактов;

d. Список правил перевода с одного языка на другой

2. Семантический словарь.
В данном словаре предполагается хранить семантические данные базы документов, которую требуется использовать в качестве исходной. При анализе текстов на заимствование потребуется выявлять наличие заимствований именно из этой базы документов.

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

В данной работе формирование базового словаря было решено выполнять на основе данных, находящихся на сервере открытого проекта WikiPedia – ВикиСловарь.

Для каждого слова в ВикиСловаре существует страница, представленная в виде разделов следующим образом:

1. Морфологические и синтаксические свойства

2. Семантические свойства

3. Синонимы

4. Антонимы

5. Родственные слова

6. Устойчивые словосочетания

7. Этимология

8. Перевод

Из данного списка полезными для построения семантического словаря могут оказаться данные, принадлежащие разделам:

1. Семантические свойства

2. Синонимы

3. Родственные слова

4. Устойчивые словосочетания

5. Этимология

6. Перевод

Данные из Викисловаря можно получить путем обращения к соответствующим html-страницам.

Для того чтобы получить доступ к любым WEB-страницам разработан соответствующий класс CWebData. У данного класса существует единственный (кроме конструктора) публичный метод

public string get_web_page(string url)

Данный метод принимает в качестве параметра адрес требуемой страницы и возвращает ее содержимое в виде одной нуль-терминированной строки.

Предполагается, что данный класс будет использован в качестве родительского для некоторых производных классов (но не обязательно: класс не объявлен как абстрактный, а следовательно может быть использован и без наследования).

Данный класс может быть унаследован для следующих целей:

1. Запрос к WEB-странице может занимать длительное время, которое нецелесообразно тратить на ожидание ответа WEB-сервера.

2. Маловероятно, что для задач анализа текста на наличие заимствований потребуется использовать в исходном (сыром) виде. В большинстве случаев потребуется сначала разобрать содержимое WEB-страницы, выделив из нее требуемые данные. Поэтому имеет смысл унаследовать от класса дочерний класс, который позволит выполнять parsing страницы и получать данные в структурированном виде.

Для доступа к WEB-страницам в данном классе используется средства, декларированные в пространствах имен System.Net, System.IO и System.Text.

Для выполнения анализа Викисловаря сначала потребуется получить список всех доступных слов. Адреса страниц со списками доступных слов в Викисловаре строятся по шаблону:

#"#">#"_Toc170623451">2.2.2. Формирование семантических моделей

Правила формирования семантических моделей для анализа текстов, представленных на естественном языке схожи с правилами построения семантической паутины.

Идея внедрения семантических сетей была предложена и сейчас курируется Тимом Берненсом-Ли в мае 2001 года и предполагает качественно новый способ хранения и обработки материалов, предоставляемых в общий доступ.

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42