Анализ текстов на заимствование методом построения семантических моделей — страница 9

  • Просмотров 17582
  • Скачиваний 409
  • Размер файла 291
    Кб

текстов, которые анализируются на наличие заимствований; ·        Максимальный и средний размеры текстов, которые рассматриваются в качестве элементов множества B; ·        Величина n; ·        Априорная информация о максимальном и среднем d Наиболее распространенные алгоритмы вычисления размера между строками представлены в таблице 2.1. Таблица 2.1 Алгоритмы вычисления расстояний

между строками N п/п Алгоритм Сложность по времени Сложность по памяти Особенности применения 1 Метод динамического программирования Вагнера и Фишера O(n, m) = (n+1)*(m+1) 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 не изменялся или выполнялись незначительные изменения. Если же выполнялись изменения исходного текста (перевод на другой язык, замена некоторых существительных