Какой алгоритм я могу использовать, чтобы найти общие смежные слова / распознавание образов?

Question

В моей базе данных есть большая таблица с множеством слов из разных текстов в текстовом порядке.Я хочу найти количество раз / частоту, с которой какой-либо набор слов появляется вместе.

Пример : Предположим, у меня есть 4 слова во многих текстах: United | States | of | America.Я получу в результате:

Соединенные Штаты : 50
Соединенные Штаты : 45
Соединенные Штаты Америки :40

(Это только пример с 4 словами, но может быть с менее чем 4).

Есть какой-то алгоритм, который может сделать это или подобный этому?

Редактировать: Приветствуется некоторый код R или SQL, показывающий, как это сделать.Мне нужен практический пример того, что мне нужно сделать.

Структура таблицы

У меня есть две таблицы: Token, которая имеет id и text.Текст: UNIQUE, и каждый элемент в этой таблице представляет собой отдельное слово.

TextBlockHasToken - это таблица, в которой хранится порядок текста.Каждая строка представляет слово в тексте.

Имеет textblockid, то есть блок текста, которому принадлежит токен.sentence - это предложение токена, position - это позиция токена внутри предложения и tokenid - это ссылка на таблицу токенов.

Answer 1

Это называется N-грамм;в твоем случае это 4 грамма.Это действительно может быть получено как побочный продукт цепи Маркова, но вы также можете использовать скользящее окно (размер 4), чтобы пройти (линейный) текст при обновлении 4-мерной «гистограммы».

ОБНОВЛЕНИЕ 2011-11-22: цепочка Маркова - это способ смоделировать вероятность перехода в новое состояние, учитывая текущее состояние.Это стохастический эквивалент «конечного автомата».В случае с естественным языком «состояние» формируется из «предыдущих N слов», что подразумевает, что вы рассматриваете предыдущую вероятность (перед предыдущими N словами) как equal_to_one.Компьютерные люди, скорее всего, будут использовать дерево для реализации цепей Маркова в случае НЛП.«Состояние» - это просто путь от корня к текущему узлу, а вероятности words_to_follow - это вероятности потомков текущего узла.Но каждый раз, когда мы выбираем новый дочерний узел, мы фактически сдвигаемся вниз по дереву и «забываем» корневой узел, окно которого имеет только N слов в ширину, что переводит N уровней глубоко в дерево.

Вы можете легко увидеть, что если вы идете по цепочке / дереву Маркова, как это, в любое время вероятность до первого слова равна 1, вероятность после первого слова равна P (w1), после второго слова = P (w2)||w1 и т. д. Итак, при обработке корпуса вы строите марковское дерево (: = обновите частоты в узлах), в конце поездки вы можете оценить вероятность данного выбора слова по freq (word) / SUM(FREQ (братья)).Для слова 5 в глубине дерева это вероятность слова, учитывая предыдущие 4 слова .Если вы хотите получить N-граммные вероятности, вы хотите, чтобы произведение всех вероятностей на пути от корня до последнего слова.

Answer 2

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

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

Answer 3

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

require(hash)

get.ngrams <- function(text, target.words) {
  text <- tolower(text)
  split.text <- strsplit(text, "\\W+")[[1]]
  ngrams <- hash()
  current.ngram <- ""
  for(i in seq_along(split.text)) {
    word <- split.text[i]
    word_i <- i
    while(word %in% target.words) {
      if(current.ngram == "") {
        current.ngram <- word
      } else {
        current.ngram <- paste(current.ngram, word)
      }
      if(has.key(current.ngram, ngrams)) {
        ngrams[[current.ngram]] <- ngrams[[current.ngram]] + 1
      } else{
        ngrams[[current.ngram]] <- 1
      }
      word_i <- word_i + 1
      word <- split.text[word_i]
    }
    current.ngram <- ""
  }
  ngrams
}

Итак, следующий ввод ...

some.text <- "He states that he loves the United States of America,
 and I agree it is nice in the United States."
some.target.words <- c("united", "states", "of", "america")

usa.ngrams <- get.ngrams(some.text, some.target.words)

... приведет к следующему хешу:

>usa.ngrams
<hash> containing 10 key-value pair(s).
  america : 1
  of : 1
  of america : 1
  states : 3
  states of : 1
  states of america : 1
  united : 2
  united states : 2
  united states of : 1
  united states of america : 1

Обратите внимание, что эта функция нечувствительна к регистру и регистрирует любую перестановку целевых слов, например:

some.text <- "States of united America are states"
some.target.words <- c("united", "states", "of", "america")
usa.ngrams <- get.ngrams(some.text, some.target.words)

... приводит к:

>usa.ngrams
<hash> containing 10 key-value pair(s).
  america : 1
  of : 1
  of united : 1
  of united america : 1
  states : 2
  states of : 1
  states of united : 1
  states of united america : 1
  united : 1
  united america : 1

Answer 4

Я не уверен, поможет ли это вам, но вот небольшая программа на Python, которую я написал около года назад, которая считает N-граммы (ну, только моно-, би- и триграммы). (Он также рассчитывает энтропию каждого N-грамма). Я использовал это, чтобы посчитать эти N-граммы в большом тексте. Ссылка