Алгоритм для поиска номера по маске

Question

[Нуржан Бакибаев]

Не могу придумать как организовать поиск по маске телефона в mysql.

Есть таблица, хранящая номера мобильных телефонов (всегда 10 цифр) — примерно 2 миллиона записей.
Нужно организовать поиск по этим номерам с помощью масок: маска также всегда состоит из 10 символов, в которых:
1) цифры 0..9 — означают что на этом месте стоит цифра
2) X — означает что может быть любая цифра
3) A,B,C,D — цифры, отличные друг от друга (A не равно B, B не равно С, ...).

Например если маска 911-AAA-X-BBB, то под неё попадают номера:
911-000-0-111
911-000-0-222
911-000-0-333
…
911-000-0-999
911-111-0-000
911-111-0-222
и т.д.
но не попадают номера
911-001-0-222 (все вхождения буквы А должны соот. одной цифре)
911-111-0-111 (A не должно быть равно В)

Пробовал сделать с помощью regexp, но вроде там нельзя реализовать логику что A!=B или что все вхождения A имеют одну и ту же цифру.

Answer 1

[balloon]

Не придумал как сделать через одну регулярку, но можно попробовать следующее:

1. Сгенерировать общую регулярку.
Для 911-AAA-X-BBB это будет выглядеть как 911-(000|111|222|...|999)-[0-9]-(000|111|222|...|999)

2. Сделать сравнение блоков A,B,C,D через подстроки.
Для 911-AAA-X-BBB это будет выглядеть как SUBSTRING(phone,5,3) != SUBSTRING(phone,11,3)

Comments

[Нуржан Бакибаев]

Второй вариант интересный. Надо попробовать. Спасибо

[Нуржан Бакибаев]

Насчет первого варианта получится слишком длинный запрос если делать проверки вида A != B

[balloon]

Я хотел сказать, что это два шага одного решения. Регулярка для общего шаблона, и потом сравнения построк для блоков A,B,C,D.

[Нуржан Бакибаев]

Вместо первой регулярки сделал LIKE и заменил все А, В, С, Х на '_'
Второй шаг оставил так же.
Вроде работает шустро. Попробую сравнить по скорости с вариантом Dzuba
Спасибо

[FilimoniC]

/911-(?:[1]{3}|[2]{3}|[3]{3}|[4]{3}|[5]{3}|[6]{3}|[7]{3}|[8]{3}|[9]{3}|[0]{3})-\d{1}-(?:[1]{3}|[2]{3}|[3]{3}|[4]{3}|[5]{3}|[6]{3}|[7]{3}|[8]{3}|[9]{3}|[0]{3})/

Answer 2

[Dzuba]

Имею 2 варианта:

Вариант 1. Хранить сами номера телефонов «поциферно» — в 10 полях таблицы (D0, D1, ..., D9), по 1 полю на каждую цифру номера. Произвести индексацию по этим полям.
Плюсы: при поиске будут использоваться индексы.
Минусы: растет размер таблицы, растет время обновления данных при вставке/замене и т.д.
Пример для маски 911-AAA-X-BBB:

SELECT * FROM table WHERE D0=9 AND D1=1 AND D2=1 AND D3=D4 AND D4=D5 AND D7=D8 AND D8=D9

Вариант 2. При вводе маски (в основной программе) заранее подготовить список ВСЕХ (не обязательно содержащихся в таблице) номеров, удовлетворяющих маске, и использовать уже этот список в WHERE.
Плюсы: при поиске будет использоваться индекс.
Минусы: при «слабой» маске, таких номеров в списке может оказаться довольно много и сам текст запроса получится невообразимо большим.
Этот метод будет хорош, когда маска «сильная», например: 911-AAAAAA-X (всего порядка 100 вариантов)
Пример для маски 911-AAA-X-BBB:

SELECT * FROM table WHERE phone IN (9110001111, 9110001222, 9110001333, ...)

Comments

[Нуржан Бакибаев]

Второй вариант рассматривали — на некоторых запросах получается по 500-600 вариантов, поэтому от этого варианта отказались.

[Нуржан Бакибаев]

Первый вариант интересный. Касательно минусов волнует только размер таблицы и индексов: насколько всё это возрастет? Для каждого индекса получается mysql строит B+ дерево, поэтому примерно O(N) доп. памяти.
Насчет времени обновления: строки добавляются в базу очень редко (за неделю добавляется примерно 50 новых строк), а обновление проходит только по другим полям (т.е. индексы затрагивать не будут).

[LeoCcoder]

мне первый вариант понравился, должно хорошо получится

[Dzuba]

Чтобы узнать на сколько возрастет размер данных, нужно знать, как сейчас хранятся номера. Если это BIGINT, то рост будет незначительным: BIGINT = 8 байт против 10 * TINYINT = 10 байт. Если сейчас CHAR(10) в однобайтовой кодировке, то занимаемое место вообще не возрастет. Это всё в предположении, что тип новых полей будет TINYINT, что мной и подразумевалось.

В отношении индексов сказать затрудняюсь, к сожалению. Моих знаний в этой области явно недостаточно, чтобы предсказать размер индексов и, тем более, поведение оптимизатора mysql при работе с ними. Поэтому я бы положился на эксперименты. Благо есть EXPLAIN.
Насколько мне известно, mysql использует только 1 индекс для подобных запросов, поэтому это тонкий момент. Быть может, имеет смысл вообще сделать единственный (и уникальный) индекс по все полям сразу. Или независимые, но лишь по части полей. А то и вовсе отказаться от индексов, в любом случае это (по моим представлениям) должно быть быстрее, чем строковый разбор номеров.

Answer 3

[Вячеслав Слинько]

regexr.com?331cn

^911-(\d)\1{2}-0-((?!\1)\d)\2\2$

Comments

[Вячеслав Слинько]

^911-(\d)\1{2}-0-((?!\1)\d)\2{2}$

матчим 911-
запоминаем первое число (\d)
проверяем что оно повторяется еще 2 раза \1{2}
матчим -0-
проверяем что следующее число не равно первому (?!\1) и запоминаем его ((?!\1)\d)
проверяем что следующее число повторяется еще 2 раза \2{2}

[Нуржан Бакибаев]

честно говоря, не очень понял.
как будет, например, для 911-ABC-X-ABC

[Вячеслав Слинько]

Для каждого паттерна нужен свой регекс

[Вячеслав Слинько]

для 911-ABC-X-ABC еще проще

^911-(\d)(\d)(\d)-\d-\1\2\3$

[Вячеслав Слинько]

regexr.com?331cq

[Вячеслав Слинько]

Упс забыл что A!=B!=C для 911-ABC-X-ABC

[Вячеслав Слинько]

Вот верный regexr.com?331ct

911-(\d)((?!\1)\d)((?!\1|\2)\d)-\d-\1\2\3

[Вячеслав Слинько]

на самом деле, если нужна проверка именно по вашей маске, можно написать простой компилятор

[Вячеслав Слинько]

могу накидать на php

[balloon]

А MySQL разве умеет запоминать блоки?

[Вячеслав Слинько]

balloon не в курсе

[Нуржан Бакибаев]

маску вводит пользователь.
Кажется MySQL не умеет запоминать блоки.

[Вячеслав Слинько]

Тогда самый простой вариант: из MySQL выбирать по мягкому паттерну (заменяя ABC на X), а после фильтровать по строгому.

[Нуржан Бакибаев]

Проблема в том что по мягкому паттерну проходят слишком много номеров: не хочется пост-но их таскать с сервера mysql на сервер glassfish.

[Нуржан Бакибаев]

Спасибо за помощь!

[Вячеслав Слинько]

Вот библиотечка, как и обещал.

Answer 4

[ertaquo]

Попробуйте использовать регулярные выражения. А именно, \d{3}-\d{3}-\d-\d{3}

Comments

[FilimoniC]

Не покатит, так как \d{3} попадет как в 111, так и в 123

Answer 5

[Александр Скляров]

911-(0{3}|1{3}|2{3}|3{3}|4{3}|5{3}|6{3}|7{3}|8{3}|9{3})-X-(0{3}|1{3}|2{3}|3{3}|4{3}|5{3}|6{3}|7{3}|8{3}|9{3})
я бы использовал такой вариант, на большее я незнаю
а вот на счет проверки что AAA =! BBB если только выдирать из номера и сравнивать их отдельно, но тут у меня возникает есть ли смысл делать это базой, я не спец в этом

Comments

[Александр Скляров]

зы myregexp.com/ давно пользуюсь этим сайтом, что бы строить такое, может конечно можно и красивее, но моих познаний не хватает, а точнее нет потребности наверно

[Александр Скляров]

сижу извращаюсь
911(-(0{3}|1{3}|2{3}|3{3}|4{3}|5{3}|6{3}|7{3}|8{3}|9{3})|(-X{0,1})){3}

Answer 6

[Dzuba]

Да, прошляпил один момент — в первом варианте нужно добавить условие, что A != B. С ним запрос будет выглядеть, например, так:

SELECT * FROM table WHERE D0=9 AND D1=1 AND D2=1 AND D3=D4 AND D4=D5 AND D7=D8 AND D8=D9 AND D3!=D7

Comments

[Dzuba]

Блин. Не туда. Это замечание относится к моему комментарию выше.