Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / PHP, Perl, Python [игнор отключен] [закрыт для гостей] / [PHP] Алгоритм сжатия / 11 сообщений из 11, страница 1 из 1
10.08.2012, 10:01:51
    #37911700
Zhenek
Zhenek
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
[PHP] Алгоритм сжатия
Добрый день.

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

Нашел более менее алгоритм, который мне понравился Алгоритм Хаффмана (можно и Фано) Суть в том, чтобы заменять частые последовательности короткими частями, а редкие длинными.

Но он кодирует все в цифры. Да и имеет ряд недостатков, в виде обязательного присутствия таблицы частот (не проблема хранить в БД) но и процент сжатия там критически мал, а то и раздует слово.

Пришла в голову мысль в БД забить таблицу замен (по типу таблицы частот)

например :

111 заменять на 11
157 на 12

и т.д т.е 3х символьные на 2х.

Но так, чтобы ни один из полученных кодов не является префиксом другого. (11122 и что тут 11 и 12 или 11 и 22)
Выходит, тоже не большое сжатие, но позволит сократить артикул ну символов на 5, что уже достаточно.

Может есть более хорошие варианты? (буквы использовать не желательно, не удобно диктовать)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.08.2012, 10:08:20
    #37911716
Anjey aka PM
Anjey aka PM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
[PHP] Алгоритм сжатия
crc32 думаю не должно иметь коллизий в случае если номеров не очень много, можно проверить.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.08.2012, 10:09:49
    #37911721
Anjey aka PM
Anjey aka PM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
[PHP] Алгоритм сжатия
то есть 16, crc16... 32 выигрыша по длине не даст.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.08.2012, 10:21:35
    #37911748
Zhenek
Zhenek
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
[PHP] Алгоритм сжатия
Спасибо большое) То что нужно)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.08.2012, 10:40:25
    #37911793
Anjey aka PM
Anjey aka PM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
[PHP] Алгоритм сжатия
Zhenek,

Сначала проверьте не будет ли коллизий.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.08.2012, 11:39:21
    #37911953
r u
r u
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
[PHP] Алгоритм сжатия
Zhenek,

у вас есть большое ДЕСЯТИЧНОЕ число
запакуйте его например в 62-тиричное ))) или еще больше
 
пример
Код: php
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
// десятичное в 62-цетиричную строку
function packInt($in) {
	$a = array_merge( range(0, 9), range('a', 'z'), range('A', 'Z') );
	$base = sizeof($a);
	$h = '';
	while($in>=$base) {
		$d1 = floor($in/$base);
		$ost = $in-$d1*$base;
		$in = $d1;
		$h .= $a[$ost];
	}
	return strrev($h.$a[$in]);
}
echo packInt(PHP_INT_MAX); // 2lkCB1



если числа очень длинные, то нужно использовать расширение gmp, и переписать под него предложенную функцию.
это как вариант
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.08.2012, 14:17:32
    #37912256
Anjey aka PM
Anjey aka PM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
[PHP] Алгоритм сжатия
r u,

Zhenek (буквы использовать не желательно, не удобно диктовать)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.08.2012, 17:30:15
    #37914923
Шогал
Шогал
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
[PHP] Алгоритм сжатия
А чем плох автоинкрементный id? Коллизии с ним невозможны, размер зависит от количества товаров в базе (а он явно меньше артикуля, иначе уникальность пропадёт), на вновь добавляемых товарах величина не увеличится резко (как это может быть с хаффманом, если строить таблицу частот по уже существующим без учёта новых, которые предугадать в общем случае невозможно).
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.08.2012, 20:26:09
    #37915124
Anjey aka PM
Anjey aka PM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
[PHP] Алгоритм сжатия
Есть подозрение, что ТС хочет иметь возможность всегда и везде привести оригинальный номер к внутреннему, в случае с автоинкрементом (который, конечно-же, прдпочтительнее) без таблицы маппинга это невозможно.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.08.2012, 20:42:29
    #37915137
miksoft
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
[PHP] Алгоритм сжатия
Anjey aka PMЕсть подозрение, что ТС хочет иметь возможность всегда и везде привести оригинальный номер к внутреннему, в случае с автоинкрементом (который, конечно-же, прдпочтительнее) без таблицы маппинга это невозможно.Ну так и пусть будет таблица.
Более того, я бы предложил этот сгенеренный id сделать первичным ключом справочника товаров. А все артикулы хранить в отдельной табличке со ссылкой на этот id. Нередко случается, когда у одного товара несколько артикулов (например, старый и новый). А иногда, хоть и редко, бывает даже наоборот, один артикул у двух товаров.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.08.2012, 09:32:23
    #37916970
Anjey aka PM
Anjey aka PM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
[PHP] Алгоритм сжатия
miksoft,

Согласен, а еще бывает что у товара несколько актуальных артикулов, в зависимости от поставщика
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / PHP, Perl, Python [игнор отключен] [закрыт для гостей] / [PHP] Алгоритм сжатия / 11 сообщений из 11, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 498ms
Закрыть
start [/forum/topic.php?fid=23&tablet=1&tid=1464807]:
 0ms
get settings:
 9ms
get forum list:
 15ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 158ms
get topic data:
 10ms
get forum data:
 2ms
get page messages:
 46ms
get tp. blocked users:
 1ms
others: 251ms
total:  498ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]