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

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

10.09.2012, 18:37. Показов 4999. Ответов 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
Ответ Создать тему
Новые блоги и статьи
Access
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
Фото: Daniel Greenwood
kumehtar 13.11.2025
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru