Методы поиска общих последовательностей слов в большом текстовом корпусе?

Question

Существуют ли алгоритмы для эффективного поиска n наиболее распространенных k-словных последовательностей слов в большом корпусе текста?

Так, например, если n = 1 и k = 5, и мой корпусis:

a b a b a c d e f a b a b a c c b c b a b c

Вывод будет a b a b a

Answer 1

Вот простой алгоритм. Разбейте последовательность слов на последовательность из k слов, в каждом слове, по одной строке. Для вашего примера у нас есть:

a b a b a
b a b a c
a b a c d
b a c d e
a c d e f
c d e f a
d e f a b
e f a b a
f a b a b
a b a b a
b a b a c
a b a c c
b a c c b
a c c b c
c c b c b
c b c b a
b c b a b
c b a b c
c b a b c

Сортировать их:

a b a b a
a b a b a
a b a c c
a b a c d
a c c b c
a c d e f
b a b a c
b a b a c
b a c c b
b a c d e
b c b a b
c b a b c
c b a b c
c b c b a
c c b c b
c d e f a
d e f a b
e f a b a
f a b a b

Теперь легко найти k-последовательность, которая является наиболее распространенной. Если файл очень большой, вам, возможно, придется разделить его, отсортировать части, а затем объединить части.