Задача хранения и поиска больших объемов данных.

[WebByte]

Задача хранения и поиска больших объемов данных.

Имеется некая практическая задача, смысл которой в следующем.

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

Надо для числовой последовательности определить страны и города,
в которых она может являться телефонным номером.

Задача, как понимаете, достаточно ресурсоемкая.
По данным может строиться несколько миллионов шаблонов.
Простым перебором решать - смерти подобно.

Я строил дерево для оптимизации поиска по следующему правилу:

Для каждого нового города строим всевозможные шаблоны согласно правилам.
Общий вид шаблона например такой:
8095\d{7} - возможный шаблон для записи московского номера.

Шаблоны упорядочиваем в общее дерево по следующему принципу.
Верхний элемент - длина шаблона. Элемент второго уровня - первые N цифр шаблона. Элемент третьего уровня - еще несколько цифр.

Число уровней и длияну ключей в принципе можно расчитать на тестах.

Последний элемент - массив вида (шаблон, ссылка на страну, ссылка на город)

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

Вот и интересно кто чего придумает еще.

 

[[DAN]]

Если отбросить шаблоны телефонных номеров, то можно сделать след. образом.

1) Составляем таблицу кодов. Например, в Гондурасе (код 504) есть коды мобильных телефонов: 38, 39 (как у нас для сотовых операторов есть коды 902, 903 и т.д.)
Тогда полный код будет выглядеть как 50438.

2) Для данной числовой последовательности последовательно с конца "отрезаем" одну цифру и ищем данную последовательность в кодовой таблице.
В принципе, если иметь проиндексированную кодовую таблицу в виде таблицы в БД, то можно одним запросом найти код(ы), соответствующий(ие) данной числ. последовательности.
Например так: [sql]SELECT code FROM table WHERE code IN('504381234567', '50438123456', '5043812345', '504381234', '50438123', '5043812', '504381', '50438', '5043', '504', '50', '5')[/sql]
Ну а определить по коду название страны и город (сотового оператора и т.д.) проблем, имхо, не составит.

PS не могу утверждать, что мой вариант оптимальнее, но все же вариант.

 

[WebByte]

Есть проблема.
Московский номер 1234567 может записываться так
70951234567 - международный формат (разделители отбрасываю)
80951234567 - межгород по России
0951234567 - без указания выхода на межгород
01170951234567 - звонок из США
71070951234567 - звонок из Казахстана
и еще куча вариантов. В зависимости от того откуда звонят и куда хотят попасть.

 

[[DAN]]

Да, тут будет посложнее.
Тогда как вариант, строить еще и таблицу префиксов и в соответствии с ней приводить номер к международному формату.

 

[B@zzy]

А так?

SELECT code
FROM TABLE WHERE code REGEXP '(011|710)?(7|8)?(095)?(\d{7})'

 

[WebByte]

На тестовых данных
- 10 мобильных операторов
- 3 области России по 3-6 городов
- страны СНГ (по 5-10 городов)
- Германия (20 городов)
получилось ~5000 шаблонов.
Представляешь как будет выглядеть запрос и как относительно долго он будет работать?

 

[f1]

я думаю, просто надо поискать документацию (теорию) как эту задачу решают телефонные коммутаторы.

 

[WebByte]

Я предполагаю, что все-таки на коммутатор звонят по определенным правилам.
Например, чтоб позвонить в Москву, надо набрать сначала 8-ку, потом код города 095 + номер телефона (всего 1+3+7= 10 цифр)

В то время как этот же номер может быть записан по-разному.
Коммутатор - не показатель, там все строго...

В принципе, алгоритм я реализовал. Работает шустро. Может, все-таки оптимальнее решения, чем построение дерева по начальным цифрам, нет?

 

[Screamer]

Насколько я знаю, телефонные номера внутри города занимают 5-7 цифр, код города - 3 цифры (могу и ошибаться). Так вот, к каждому шаблону приписать параметр количества цифр, после этого при поиске отрезаем 7 последних цифр номера и ищем только в шаблонах с 7-значными номерами, потом отрезаем 6 цифр, потом 5. Кроме того, код города не меняется, меняется код доступа, тоже можно раздельно искать. Таким образом, есть таблица городов, у каждого города есть код(ы), количество цифр в номере и набор префиксов исходящих звонков

 

[WebByte]

Ошибаешься.
Смотри.
Код Владивостока, если звонить из Москвы 4232.
А если звонить из соседнего города 22. Нюансов полно.
Вопрос не только в том КАК искать, но и как организовать дерево для поиска...

 

[Mammoth]

Надо отталкиваться от кол-ва цифр в номере: по-моему, все международные номера имеют 11 цифр. Если длина телефона меньше, - значит номер указан без кода страны/города или с кодом дозвона из той же зоны (пример дозвона до Владивостока из соседнего города).

 

[[DAN]]

Тут однозначно нельзя завязываться на длине номера.
Для Германии, допустим, мобильный номер может содержать до 15 знаков, а в российском городе номер может быть из 5 знаков (локальный городской).

Имхо при такой постановке задачи все-таки самым шустрым вариантом будет дерево.

Хотя и такой вариант покатит: строим таблицу с шаблонами и в этой таблице каждому шаблону сопоставляем правило преобразования номера в международный формат. Далее http://phpclub.ru/talk/showthread.php?postid=393523#post393523

-~{}~ 21.10.04 19:07:

WebByte
>Может, все-таки оптимальнее решения, чем построение дерева по начальным цифрам, нет?

В дереве есть вот какая опасность. Допустим, мы имеем на входе 237775533.
Что это за номер? С одной стороны смахивает на номер в Камеруне, с другой на локальный межгород. Как все-таки однозначно определить, что это за номер? Если бежать по дереву, то выдастся первый (и единственный имхо) вариант.