0 / 0 / 0
Регистрация: 16.03.2010
Сообщений: 40
1

Как ускорить алгоритм шинглов?

10.09.2012, 18:37. Показов 4622. Ответов 3
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Итак есть алгоритм шинглов для сравнения двух текстов на похожесть. Реализация была найдена в инете и спасибо ее автору. Вот ее код:
PHP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
<?
//очистка текста от незначащих частей
function canonize($text){
//стоп-символы
$stop_symbols = array (
"1", "2", "3", "4", "5", "6", "7", "8", "9", "0",
"~", "`", "!", "@", "\"", "#", "№", "$", ";", "%",
"^", ":", "&", "?", "*", "(", ")", "-", "_", "+",
"=", "\t", "{", "[", "]", "}", "\r", "\n", "\\", "/",
"|", ",", ".");
//убираем стоп-символы
$text = str_replace($stop_symbols, '', $text);
//убираем дублирование пробели
while (strpos($text, '  ')!=false)
    {
    $text = str_replace('  ', ' ', $text);
    }
//приводим все символы к нижнему регистру
$text=strtolower($text);
//разбиваем на слова
$words = split(' ', $text);
return $words;
}
 
//получение набора шинглов из массива слов
function get_shingles($word_arr){
//количество слов в шингле
$shingleLen = 3;
for ($i=0;$i<(count($word_arr)-$shingleLen+1);$i++)
    {
    $shingle='';
    for ($j=0;$j<$shingleLen;$j++)
        {
        $shingle.=$word_arr[$i+$j];
        }
    $shingles[] = md5($shingle);
    }
return $shingles;
}
 
//возвращает процент схожести текста
function compare_shingles($shingle1, $shingle2){
//лучше если первым будет идти больший массив шинглов
if (count($shingle2)>count($shingle1))
    {
    $shingle_tmp=$shingle1;
    $shingle1=$shingle2;
    $shingle2=$shingle_tmp;
    }
$diff=array_diff($shingle1, $shingle2);
$count_shingle_diff=count($diff);
$count_shingle=count($shingle1);
return ($count_shingle-$count_shingle_diff)/$count_shingle*100;
}
 
//сравнение двух текстов на схожесть
function compare_text($text1, $text2){
    $shingle1=get_shingles(canonize($text1));
    $shingle2=get_shingles(canonize($text2));
    return compare_shingles($shingle1, $shingle2);
}
?>
У меня в базе будет около 30000 текстов длинной от 3000 до 10000 слов. И мне нужно будет мой текст, который я ввожу для проверки (приблизительно такой же длинны) прогнать по всей базе и найти максимальный процент сходства. Но тут и вся загвоздка, что времени уйдет на проверку очень много. Может кто сталкивался с подобной задачей? Какие есть идеи по ускорению проверки?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
10.09.2012, 18:37
Ответы с готовыми решениями:

Перевести код алгоритма шинглов из PHP в Delphi
Добрый день! Прошу помочь перевести код из PHP в Delphi. Кому не сложно, очень прошу! Это не для...

Как ускорить алгоритм
#include&lt;stdio.h&gt; min(int x,int y) { if(x&lt;y) return x; else return y; } main() {

Последовательности чисел: как улучшить / ускорить алгоритм?
Задание: Для заданной последовательности неотрицательных целых чисел необходимо найти...

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

3
2386 / 2250 / 584
Регистрация: 27.05.2011
Сообщений: 7,709
11.09.2012, 10:45 2
а чем вам не подходит дефолтаная функция нахождения схожести текста similar_text() ?
0
0 / 0 / 0
Регистрация: 16.03.2010
Сообщений: 40
31.10.2012, 17:07  [ТС] 3
Цитата Сообщение от crautcher Посмотреть сообщение
а чем вам не подходит дефолтаная функция нахождения схожести текста similar_text() ?
Данная функция плохо работает с кириллицей. и плюс - это дипломная работа и мне нужно использовать какой-то алгоритм, а не дефолтную функцию. в интернете все хвалят этот алгоритм. и пробуют использовать. А может есть другие идеи по тому, как сравнить тексты и получить процент схожести.
0
6 / 6 / 6
Регистрация: 21.12.2011
Сообщений: 60
14.05.2016, 11:15 4
Алгоритм вообще не работает,
например
PHP
1
2
3
$str1= 'ООО "БИгМол+Л"';
$str2 = 'Белгородский молочный комбинат ';
echo "<pre>"; print_r(compare_text($str1,$str2)); echo "</pre>";
выведет 100
PS: similar_text() нормально себя ведет с кириллицей
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
14.05.2016, 11:15
Помогаю со студенческими работами здесь

Как ускорить данный алгоритм нахождения минимума на отрезке?
Здравствуйте, подскажите, пожалуйста, почему решение не проходит по времени на нескольких тестах?...

Как сократить алгоритм , что бы ускорить время выполнения
Всем Доброго времени суток ;D Подскажите пожалуйста как можно преобразовать код , либо...

Как ускорить алгоритм. Нахождение максимальной суммы подряд идущих элементов
Собственно САБЖ, делал программу , которая находит сумму элементов массива.. на данный момент самый...

Ускорить алгоритм
Есть код который сохраняет строку из StringList в 2-ой StringList, если этой строки нет в 3-ий...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru