кол-во словосочетаний в тексте и др.

[maxx]

кол-во словосочетаний в тексте и др.

Доброго времени суток!

Проблема: есть текст, необходимо подсчитать кол-во повторений двух, трех или четырех слов. Думаю на примере (для сочетания 2 слов) будет все понятно:

есть 4 слова в тексте А, Б, В, Г. текст такой:
А Б В Г В А Б Г В А Г Б.

результат:
А Б : 2 раза
Б В : 1 раз
В Г : 1
Г В : 2
В А : 2
Б Г : 1
А Г : 1
Г Б : 1

как я это делаю сейчас (только для сочетания 2 слов): каждое слово в тексте имеет позицию (первое, второе и т.д) я строю таблицу вхождений:
А: 0, 5, 9
Б: 1, 6, 11
В: 2, 4, 8
Г: 3, 7, 10

и при помощи 4 вложенных циклов прохожу по сочетаниям позиций и если позиции отличаюца на 1 то сохраняю...

на 400 словах работает 1.3 секунды и ест 10% ресурсов сервера.

ВОПРОС: мне еще нужно ведь для трех и четырех слов построить... есть ли более "правильный" и быстрый алгоритм?

 

[valyala]

/**
    Функция count_combinations(). Автор: valyala ([email protected])
    Подсчитывает количество повторений цепочек слов в массиве.
    Параметры:
        $words - массив подряд идущих слов, для которых нужно подсчитать количество повторений
        $chain_length - длина цепочки, для которой ведется подсчет
    Возвращает ассоциативный массив вида [ комбинация => счетчик ]
*/
function count_combinations($words, $chain_length) {
    $delimiter = ' '; // разделитель слов, использующийся в индексе
    $tmp = array(); // массив счетчиков различных комбинаций
    $n = sizeof($words) - $chain_length + 1; // количество итераций цикла while
    $i = 0;
    while ($i < $n) {
        $index = implode($delimiter, array_slice($words, $i, $chain_length)); // текущая цепочка слов длиной $chain_length
        if (!isset($tmp[$index])) $tmp[$index] = 1; // комбинация встретилась впервые
        else $tmp[$index]++; // комбинация уже встречалась
        $i++;
    }
    return $tmp;
}

 

[sage]

maxx

Судя по твоей таблице вхождений, пробела между буквами нет. Правильно? Тогда:

$string = "АБВГВАБГВАГБ";
$symb = array();
for ($a = 0; $a < strlen($string); $a++) {
 $symb[] = substr($string,$a,2);
}
for ($b = 0; $b < sizeof($symb); $b++) {
 $s = substr_count($string, $symb[$b]); 
 print $symb[$b] . ": " . $s . "<br>\n";
}

Здесь я использовал [m]substr_count[/m]

 

[maxx]

спасиьбо за ответы.
я над своим способом тоже немного посидел и оказалось что один из вложенных массивов не нужен. В результате я уменьшил время выполнения до 0.051 секунды
думаю такой вариант меня устроит. но как нибудь на досуге попробую и предложенные способы...

 

[Demiurg]

[m]array_count_values[/m]
как разбить текст на слова - другой вопрос.

 

[valyala]

Судя по твоей таблице вхождений, пробела между буквами нет. Правильно?

sage, какие еще буквы? Внимательно прочти вопрос:

Проблема: есть текст, необходимо подсчитать кол-во повторений двух, трех или четырех слов.

И найди в нем хоть одно упоминание про буквы.
Ну да ладно, будем считать, что ты невнимательно прочитал вопрос. Но даже в этом случае приведенный тобой PHP-код не справляется с подсчетом различных цепочек букв. Проверь, что выдает функция substr_count() вот на таком примере:

print(substr_count('abababab', 'aba'));

А теперь подсчитай самостоятельно, сколько раз встречается подстрока 'aba' в строке 'abababab'.

Пару слов о твоем стиле программирования.

Программировать - значит понимать (Кристин Нюгард)

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

for ($a = 0; $a < strlen($string); $a++) {}
for ($b = 0; $b < sizeof($symb); $b++) {}

Запомни: выражение, стоящее на втором месте в конструкции for (в нашем случае это $a < strlen($string) и $b < sizeof($symb)), выполняется в начале КАЖДОЙ итерации цикла, а не один раз при первом входе в цикл. Да, функции strlen() и sizeof() в РНР работают очень быстро, т.к. длины строки и массива заранее известны. Но если ты так напишешь под Cи, то автоматически увеличишь время выполнения цикла на порядок (справедливости ради стоит отметить, что в Си sizeof - не функция, а оператор. Это значит, что его вычисление производится на стадии компиляции. Да и вообще, sizeof в Си и в РНР выполняют совершенно разные роли).
Поэтому такие циклы лучше переписать вот так:

$n = strlen($string);
for ($a = 0; $a < $n; $a++) {}
$n = sizeof($symb);
for ($b = 0; $b < $n; $b++) {}

p.s. Каждый волен писать программы так, как ему нравится. Я всего лишь высказываю свою точку зрения.

 

[Demiurg]

valyala
причем тут С ?

>Это значит, что его вычисление производится на стадии компиляции.
не значит. for - тоже не функция.

 

[sage]

valyala
а как тебе такое?

$string = "abababab"; 
function count_comb($string,$num) {
 $n = strlen($string) - 1;
 $a = 0; 
 $symbols = array();
 for($a; $a < $n; $a++) {
  $symbols[] = substr($string,$a,$num); 
 }
 return $symbols;
} 

print_r(array_count_values(count_comb($string,3)));

 

[valyala]

причем тут С ?

Ни при чем. Я высказал свое мнение по поводу не очень удачного с точки зрения производительности стиля программирования.
Хорошо, приведу другой пример. Допустим, у нас есть очень ресурсоемкая функция get_count(), вычисляющая количество элементов, каким-либо образом связанных с ресурсом $res. (Например, $res - это хэндлер какой-нибудь СУБД, а функция get_count() при каждом вызове обращается к СУБД для получения данных, на основе которых вычисляет количество элементов). Надеюсь, не нужно объяснять, какой цикл будет эффективнее:

for ($i = 0; $i < get_count($res); $i++) {}

или

$n = get_count($res);
for ($i = 0; $i < $n; $i++) {}

>Это значит, что его вычисление производится на стадии компиляции.
не значит. for - тоже не функция.

Да, for - не функция Я неправильно выразился. Надо было сказать так: все современные Си-компиляторы вычисляют результат оператора sizeof на стадии компиляции.

-~{}~ 09.04.04 12:33:

sage, два примера, на которых твоя функция count_comb() глючит:

$string = 'abababab';
print_r(array_count_values(count_comb($string,1))); // подсчитай количество символов [b]a[/b] и [b]b[/b] в строке
print_r(array_count_values(count_comb($string,10))); // вообще-то мы хотели узнать статистику для цепочек символов длиной 10

sage, ты слабо видишь? или ты невнимательный? Прочти десять раз это предложение:

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

Тут говорится про СЛОВА, а не про СИМВОЛЫ

 

[maxx]

Автор оригинала: Demiurg
[m]array_count_values[/m]
как разбить текст на слова - другой вопрос.

на слова я режу preg_match, функция аррей_каунт в принципе мне немного упростит работу. сенкс.