С Новым годом! Форум программистов, компьютерный форум, киберфорум
PHP: базы данных
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.77/26: Рейтинг темы: голосов - 26, средняя оценка - 4.77
0 / 0 / 0
Регистрация: 16.03.2010
Сообщений: 40

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

10.09.2012, 18:37. Показов 5032. Ответов 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
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
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
 Аватар для crautcher
2450 / 2301 / 597
Регистрация: 27.05.2011
Сообщений: 7,844
11.09.2012, 10:45
а чем вам не подходит дефолтаная функция нахождения схожести текста similar_text() ?
0
0 / 0 / 0
Регистрация: 16.03.2010
Сообщений: 40
31.10.2012, 17:07  [ТС]
Цитата Сообщение от crautcher Посмотреть сообщение
а чем вам не подходит дефолтаная функция нахождения схожести текста similar_text() ?
Данная функция плохо работает с кириллицей. и плюс - это дипломная работа и мне нужно использовать какой-то алгоритм, а не дефолтную функцию. в интернете все хвалят этот алгоритм. и пробуют использовать. А может есть другие идеи по тому, как сравнить тексты и получить процент схожести.
0
 Аватар для sh1ft.
6 / 6 / 6
Регистрация: 21.12.2011
Сообщений: 60
14.05.2016, 11:15
Алгоритм вообще не работает,
например
PHP
1
2
3
$str1= 'ООО "БИгМол+Л"';
$str2 = 'Белгородский молочный комбинат ';
echo "<pre>"; print_r(compare_text($str1,$str2)); echo "</pre>";
выведет 100
PS: similar_text() нормально себя ведет с кириллицей
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
14.05.2016, 11:15
Помогаю со студенческими работами здесь

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Новые блоги и статьи
Модель микоризы: классовый агентный подход 3
anaschu 06.01.2026
aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR
ФедосеевПавел 06.01.2026
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .
Модель микоризы: классовый агентный подход 2
anaschu 06.01.2026
репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .
Расчёт токов в цепи постоянного тока
igorrr37 05.01.2026
/ * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03
palva 04.01.2026
Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .
Модель микоризы: классовый агентный подход
anaschu 02.01.2026
Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост.
Programma_Boinc 28.12.2025
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / **********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / **********/ gallery/ bKBkQFf Пост отсюда. . .
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
Programma_Boinc 26.12.2025
Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru