Выбор 10-ти наиболее часто встречающихся слов в тексте.

[dub]

Выбор 10-ти наиболее часто встречающихся слов в тексте.

Проблема: есть текст, необходимо выбрать из него 10 слов наиболее часто повторяющихся в нем, желательно учитывать префиксы, суфиксы, также учесть стоп слова("и", "в","или"....). Текст находится в базе MySql. Вопрос: Каким образом решить эту проблему наиболее оптимально(относительно скорости работы)?

Пока вижу только одно решение выбрать текст, удалить стоп слова (к стати, встрачал ли кто списочек этих слов для русского языка?), разбить текст на слова explode(" ", $text);, положить слова в массив и дальше array_search() по массиву считаем одинаковые слова c учетом префиксов суфиксов. ложим результат в массив['слово'] = sum. переходим к следующему элементу. потом из результирующего массива выбираем 10 ключей где sum наибольшее. Можно еще сделать подсчет слов с использованием array_count_values() - но как тут быть с префиксами суфиксами?

Может кто видел готовые решения, или решал подобные задачи?

 

[Фанат]

только не array_search, а array_count_values()

Может кто видел готовые решения, или решал подобные задачи?

Может, кто хоть раз в жизни попробует приложить собственную голову и руки к своей работе, а не побежит, по привычке, побираться на паперть?

 

[dub]

только не array_search, а array_count_values()

учту.

Может, кто хоть раз в жизни попробует приложить собственную голову и руки к своей работе, а не побежит, по привычке, побираться на паперть?

Собственно я не говорю сделайте мне то, или это. Я просто спрашиваю совета по тому как сделать более правильно, красиво и быстро, вот и все. Сделать то самому интересно.

 

[Alexandre]

выбрать текст, удалить стоп слова, разбить текст на слова explode(" ", $text);, положить слова в массив и дальше array_search() по массиву считаем одинаковые слова c учетом префиксов суфиксов

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

array {
[0] = выбрать 
[1] = текст,
[2] = стоп 
[3] = слова,
}

Вообщето есть словарь Лебедева , по которому можно идентифицировать одинаковые слова с разными окончаниями или суффиксами (слова, слово, словом, слов ).

 

[phprus]

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

А лучше до разбивки заменить все знаки препинания на пробелы после чего заменить все подрят идущие пробелы на 1 пробел, и только потом уже разбивать на слова при помощи explode.

 

[Wicked]

phprus
проще уж тогда preg_match_all сделать, вытаскивая все слова

 

[phprus]

Wicked
Тогда можно вообще preg_split. Так как именна эта функция преднозначенна для разбивания строки по регулярному выражению.

 

[WP]

Я бы сделал preg_match_all + stemmer.

 

[AnToXa]

господа, я понимаю, что это надо сделать в php и premature optimization is the root of all evil, но тут у вас просто premature pessimization.
представляете себе O() complexity тут и порядки констант?

1. preg_split, жесть, N копирований на каждое слово (это я молчу про сложность автомата, который пройдется по этому тексту) т.е. как минимум O(2*K) + O(N), где K - длина текста, N - кол-во слов.
2. вставка в массив, это hash lookup + вычисление hash fn, это O(N) + O(K), т.е. N инсертов и каждый раз мы проходимся по всему слову, чтобы вычислить hash_val, complexity самой вставки - O(1) в хорошем случае.
3. выборка максимальных 10, ну ессно в простом решении это сортировка, т.е. O(N * logN) сравнений, каждое есть O(M), где M - кол-во символов в слове.

ну в общем вы понимаете

 

[phprus]

AnToXa
Мы не ищем самое быстрое решение. (Это не тема про проверку числа на четность) Мы рассуждаем на тему с помощью каких функций удобнее реализовать нужную автору функциональность.

P.S. Или все таки эта тема будет развиваться по сценарию развития темы, где мы проверяли число на четность?

 

[dub]

Итак убираем стоп слова, потом preg_match_all (preg_split) выбираем буквы и БУКВЫ русского и английского алфавита + цифры, + "-" из текста. Затем array_count_values(), для простейшего варианта. А для более сложного используем stemmer ( Интересно а сколько их есть на php и под русский язык?) и работаем с помощью него с получившимся массивом.

 

[AnToXa]

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

 

[phprus]

AnToXa
Спасибо за поздравления. Но я все же не понимаю зачем в данной теме нужна эта информация? Мы же тут не оптимизацией кода занимаемся.

dub

Интересно а сколько их есть на php и под русский язык?

Один точно есть. Поищите на форуме forum.dklab.ru (точную ссылку к сожалению не помню).

 

[AnToXa]

phprus
если вас задевает что-то, напишите письмо модератору.
а пока модератор не против - у нас тут свобода слова.
на мой взгляд в данном топике напоминание о том что все это небесплатно - вполне полезно, потому и пишу.

 

[dub]

phprus
пасиба ...
http://forum.dklab.ru/php/advises/HeuristicWithoutTheDictionaryExtractionOfARootFromRussianWord.html

 

[Alexandre]

AnToXa+1 за мысль
алгоритм приблизительно такой
читаем данные из потока (поток может быть любым, из памяти, файловым, из сокета и т.д.) посимвольно.
каждый символ сравниваем по диапазону русск (анг) символов, если он вписывается в диапазон, то приклеиваем его в конец слова.
если он не вписывается в диапазон, то конец слова, символ пропускаем, а слово пишем в хештаблицу или, как ключ ассоциативный масив.
Проверяем на наличие ключа
если ключа нет - добавляем ключ - значение =1
если ключ имеется, то значение +1
переменную со значением принятого слова сбрасываем в ""

по окончания прочтения потока имеем - хештаблицу слов результат которой - кол-во повтороний.

А) Морфология не учитывается.
Б) Таблица не отсортирована.
сортируем таблицу по значению и выбираем первые 10 ключей.

должно работать быстро. Если делать на С, то использовать надо полученный хеш переписать в SotredHashTable и взять только первые 10 эл.

 

[AnToXa]

1. поток должен быть конечным, если мы хотим потом как-то сортировать.
2. сортировать полностью не нужно. если нужно первых 10 выбрать, то можно сортировать частично и тогда сложность O(N * log(сколько нам нужно, т.е. 10)), это если не выпендриваться, а если выпендриваться, то можно частично сортировать прям на лету, механизмом подобным timer wheels(http://lwn.net/Articles/156329/), а дальше уже досортировывать только старшую группу.

 

[Alexandre]

1. поток должен быть конечным, если мы хотим потом как-то сортировать.

однозначно, поток - либо http://ru.php.net/manual/en/ref.stream.php, либо fopen, fsockopen

2. сортировать полностью не нужно. если нужно первых 10 выбрать

можно выбрать первые 10 пузырьковым алгоритмом и не выеживаться, а быстрее будет - сортировать налету,
тогда - делаем массив top10, в котором храним первые 10 (int)максимальных результатов. Притом сортировать в порядке убывания/возрастания их не обязательно.

кстати, перед переписью слова в хешмассив, можно проверить его наличие на
- короткие слова (предлоги, местоимения, союзы) 1-2 символа - отсеиваем по длинне.
- слова паразиты, месстоимения, прочие не информативные слова (что, где, когда, иногда, потому, этому, ну, вообще, супер, круто, блин....)

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

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

есть идеи?

 

[AnToXa]

гхм? наверное я тебя не так понял, но как aspell влияет на сортировку всего?
aspell ведь прикручивается к стадии выборки слов, так что просто в структуры данных, которые мы будем сортировать каким-то образом не будут попадать слова которые ты не хочешь или будут попадать исправленые слова или еще каким-то образом преобразованые, но выборка 10 чего-то по какому-то критерию никак не пересекается с тем как это "что-то" формируется.

 

[Alexandre]

наверное я тебя не так понял, но как aspell влияет на сортировку всего?

ни как

aspell ведь прикручивается к стадии выборки слов, так что просто в структуры данных, которые мы будем сортировать каким-то образом не будут попадать слова которые ты не хочешь или будут попадать исправленые слова или еще каким-то образом преобразованы

+1
да, смотри что я откапал http://snowball.tartarus.org/algorithms/russian/stemmer.html с ссылки от dub отсюда есть идея - делать совмещенный алгоритм, после вычленения слова - мы его стримим (выделяем корень) и потом уже корень пишем в хештаблицу (ну и соответственно по корню осуществляем подсчет слов)

хотя это так - мысли.