Выбираем логин на Яндекс.Почте

Много лет назад я зарегистрировал себе несколько трех- и четырехсимвольных адресов на Яндекс.Почте. Они оказались очень удобными, потому что их легко писать и диктовать, особенно вместе с доменом ya.ru.

Спустя время решил проверить, остались ли еще свободные короткие адреса и есть ли среди них какие-то поинтересней. Я предполагал, что сейчас уже ничего подобного не найти. Но когда начал вбивать разные варианты в форму на странице регистрации, то понял, что шансы пока есть. Не удовлетворившись парой выпавших логинов, решил комплексно изучить вопрос.

В статье вы найдете все, что вряд ли хотели знать, но теперь имеете отличную возможность узнать, о формате и количестве логинов Яндекса, а также датасет, с помощью которого сможете попробовать разобраться с «6-q» аномалией (у меня не получилось).

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

Подсчет количества логинов

Валидность и неразличимость

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

длина логина от 1 до 30 символов
допустимые символы: буква английского алфавита в любом регистре, арабская цифра, точка и тире
первым символом может быть только буква
последним символом может быть либо цифра, либо буква
две точки и два тире подряд, а также сочетания точек и тире (.-, -.) запрещены

Соответствующие ошибки, которые возвращает валидатор

login.long login.prohibitedsymbols login.startswithdot login.startswithhyphen login.startswithdigit login.endwithdot login.endswithhyphen login.doubleddot login.doubledhyphen login.hyphendot login.dothyphen

Кроме того, не делается различий между точкой и тире, а сам логин является регистронезависимым. Это написано на странице помощи при регистрации аккаунта.

Таким образом, при подсчете логинов нужно учитывать как условия валидности, так и условия неразличимости. Поэтому далее тире считается точкой, а буквы используются только в нижнем регистре.

Общая формула

Введем обозначения

$L = \{\text{a}, \text{b}, \dots, \text{y}, \text{z}\}, \\ D = \{0, 1, \dots, 8, 9\},$

где — латинский алфавит, — арабские цифры.

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

$\sum\limits_{n=1}^{30} n^{26 + 10 + 1} \approx 6.3 \cdot 10^{54}.$

Обозначим f(n) — количество валидных логинов длины . Согласно условиям,

$f(1) = |L| = 26, \\ f(2) = |L| \cdot |L \cup D| = 936, \\ f(3) = |L| \cdot (|L \cup D| + 1) \cdot |L \cup D| = 34 632.$

Начиная с n = 3 в логине допускаются точки. Посмотрим на возможные расположения точек в логине (в скобках перечислены позиции точек):

1 x         () 2 xx        () 3 x•x       (2) 4 x•xx      (2) 4 xx•x      (3) 5 x•xxx     (2) 5 xx•xx     (3) 5 xxx•x     (4) 5 x•x•x     (2, 4) 6 x•xxxx    (2) ... 6 x•x•xx    (2, 4) 6 xx•x•x    (3, 5) ... 8 x•x•x•xx  (2, 4, 6) 8 x•x•xx•x  (2, 4, 7) 8 x•xx•x•x  (2, 5, 7) 8 xx•x•x•x  (3, 5, 7) ...

Заметим, что в логине длины может содержаться не более $m = \left\lceil \frac{n}{2} \right\rceil - 1$ точек. Таким образом, здесь и ниже считаем, что

точек, длина логина должна удовлетворять неравенству

$n \geqslant 2m + 1.$

Обозначим g(n,m) — количество валидных логинов длины с точками. Пользуясь основными правилами комбинаторики, можно выписать следующее выражение

$g(n,m) = |L| \cdot |L \cup D| \cdot P(n,m) \cdot |L \cup D|^{n-m-2},$

где P(n,m) — количество вариантов расположения точек в логине длины . В этом случае f(n) принимает вид

$f(n) = \sum\limits_{m=0}^{\lceil \frac{n}{2} \rceil - 1} g(n,m).$

Под спойлером показано, что

$P(n,m) = \binom{n-m-1}{m}.$

Вывод выражения для P(n, m)

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

Заметим, что P(n,0)=1, P(n,1) =n-2 . Рассмотрим алгоритм генерации всех возможных конфигураций расположения $m \geqslant 2$ точек в логине длины $n \geqslant 5$ :

первую точку можно размещать на любой позиции с условием $2 \leqslant k \leqslant k_{\max}$ , при этом $k_\max$ определяется из условия, что на оставшейся части логина длины должны поместиться точка, то есть

$n-k \geqslant 2\cdot(m-1)+1 \\ k \leqslant n-2m+1$

вторая точка размещается аналогично первой и т.д.

Таким образом, для каждой выбранной позиции первой точки , имеем P(n-k,m-1) вариантов расположения оставшихся точек, то есть

$P(n,m) = \begin{cases} \sum\limits_{k=2}^{n-2m+1} P(n-k,m-1) &\text{if } m \geqslant 2, \\ n-2 &\text{if } m = 1, \\ 1 &\text{if } m = 0. \end{cases}$

Посчитаем

$P(n,2) = \sum\limits_{k=2}^{n-3} P(n-k,1) = \sum\limits_{k=2}^{n-3} (n-k-2) = \sum\limits_{l = 1}^{n-4} l = \cfrac{(n-3)(n-4)}{2}$

Аналогично,

$P(n,3)=\cfrac{(n-6)(n-5)(n-4)}{6}.$

Пользуясь методом математической индукции покажем, что при $m \geqslant2$

$P(n,m) = \cfrac{1}{m!} \prod\limits_{k=1}^{m} (n-m-k) = \cfrac{(n-m-1)!}{m!(n-2m-1)!} = \binom{n-m-1}{m}$

База индукции m=2 :

$P(n,2) = \cfrac{1}{2} (n-2-1)(n-2-2) = \cfrac{(n-3)(n-4)}{2}.$

Переход: предположим, что

$P(n,m-1) = \binom{n-m}{m-1},$

тогда

$P(n,m) = \sum\limits_{k=1}^{n-2m} P(n-k-1,m-1) = \sum\limits_{k=1}^{n-2m} \binom{n-k-1-m}{m-1} = \\ = \sum\limits_{l=m-1}^{n-m-2} \binom{l}{m-1} = \binom{n-m-1}{m},$

что и требовалось доказать. Здесь мы воспользовались свойством биномиальных коэффициентов Hockey-stick identity.

Тогда общее число валидных логинов определяется выражением

$N = \sum\limits_{n=1}^{n_{\text{max}}} f(n) = \sum\limits_{n=1}^{n_{\text{max}}} \sum\limits_{m=0}^{\lceil \frac{n}{2} \rceil - 1} g(n,m) = \\ = |L| \cdot |L \cup D| \sum\limits_{n=1}^{n_{\text{max}}} \sum\limits_{m=0}^{\lceil \frac{n}{2} \rceil - 1} \cdot \binom{n-m-1}{m} \cdot |L \cup D|^{n-m-2}.$

При $n_\max = 30$ получаем $N \approx 7.7 \cdot 10^{46}$ , то есть примерно в 80 миллионов раз меньше, чем количество логинов без ограничений на расположение точек и первый и последний символы.

Генерация логинов и определение доступности

Краткое описание алгоритма:

сначала генерируются первый и последний символы согласно ограничениям
для средней части логина генерируются допустимые конфигурации расположения точек
для каждой из конфигураций точек в свободных местах проставляются числа и буквы

Реализация на Python тут (GitHub). На всякий случай прикладываю под спойлер

from math import ceil  L = 'abcdefghijklmnopqrstuvwxyz' D = '0123456789' S = '.'  def get_symbols(n):   if n > 0:     for i in L+D:       g = get_symbols(n-1)       for item in g:         yield [i] + item   else:     yield []  def get_points_pos(n, m, shift=0):   if m > 0 and n > 1 and m <= ceil(n/2):     for i in range(1, n-2*m+1):       g = get_points_pos(n-1-i, m-1, shift+i+1)       for item in g:         yield (i+shift,) + item   else:     yield ()  def get_logins_middle_part(n):   if n > 2:     for m in range(0, ceil(n/2)):       for points_pos in get_points_pos(n,m):         for symbols in get_symbols(n-m-2):           yield ''.join([             symbols.pop(0) if i not in points_pos else '.'              for i in range(1, n-1)           ])   else:     yield ''  def get_logins(n):   for first_symbol in L:     if n > 1:       for last_symbol in L+D:         g = get_logins_middle_part(n)         for item in g:           yield first_symbol + item + last_symbol     else:       yield first_symbol        print(len(list(get_logins(4))))

Определение доступности сводится к генерации всех логинов и проверке каждого через POST-запрос. В итоге была собрана текстовая таблица с данными.

Результаты анализа доступности логинов

В качестве инструмента для работы с датасетом был выбран R (Tidyverse). Файл с данными и код для обработки можно найти в репозитории. Результаты анализа ниже.

Всего имеется 1 280 448 валидных четырехсимвольных логинов. Из них на момент проверки было свободно 213 895, то есть 16.7%.

Зависимость между доступностью логина и его символами

Это первое, что приходит в голову посмотреть:

Как читать: 92% для символа «a» означает, что среди всех логинов длины 4, содержащих символ «a», занято 92%

Как читать: 97 на пересечении «а» и «b» означает, что среди всех логинов длины 4, содержащих комбинацию «ab», занято 97% (чем темнее, тем свободней)

Как читать: 90 на пересечении «1» и «a» означает, что среди всех логинов длины 4, содержащих символ «a» на первой позиции, занято 90% (чем темнее, тем свободней)

Самый заметный и интересный факт — высокая доступность логинов, содержащих символы q и 6. Кроме этого, заняты почти все логины, содержащие точку. Но в целом создается впечатление, что зарегистрировать логин со своими инициалами или днем рождения по-прежнему можно.

Распределение логинов по форматам

Разобьем логины на группы по форматам. Например, к группе a.11 отнесем все логины, у которых на первом месте буква, на втором — точка, а на третьем и четвертом — цифры.

Распределение логинов по форматам

Формат  Свободно /   Всего     Доля   a.11         1 /   2 600 ( 0.04%)   a111       121 /  26 000 ( 0.47%)   a.aa       157 /  17 576 ( 0.89%)   aa.1        94 /   6 760 ( 1.39%)   aa.a       269 /  17 576 ( 1.53%)   aaaa     9 924 / 456 976 ( 2.17%)   a.a1       244 /   6 760 ( 3.61%)   a1.1        98 /   2 600 ( 3.77%)   a1.a       274 /   6 760 ( 4.05%)   aa11     2 909 /  67 600 ( 4.30%)   a.1a       559 /   6 760 ( 8.27%)   aaa1    37 969 / 175 760 (21.60%)   a11a    19 769 /  67 600 (29.24%)   a1aa    55 858 / 175 760 (31.78%)   a1a1    22 589 /  67 600 (33.42%)   aa1a    63 060 / 175 760 (35.88%)

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

Удобные логины

На этом этапе возникло желание определить понятие «удобного» логина и посмотреть, сколько из них остается свободными. В первую очередь установим дополнительные ограничения для таких логинов:

не содержат английских букв, которые сложно распознать на бумаге или на слух
не содержат точек и цифр

Перечислю буквы, которые, как мне кажется, не подходят для email:

i и l похожи друг на друга
o похожа на 0
q, j, w, e, r, y, u, g, h, c, v, s, z собеседник может не узнать или перепутать на слух (цэ как русская эс, и как русская е и тд)

Таким образом, «удобный» логин должен состоять из легкопроизносимых, узнаваемых на слух и однозначночитаемых букв t, p ,a, d, f, k, x, b, n, m. Заметим, что среди них есть только одна гласная буква. Таких логинов 10 000. Но среди них есть логины вида namp, anam, dpdb, которые сами по себе произносятся сложно. Красивое произношение, на мой взгляд, имеют логины вида ppdk, tpda, fdkx, mnpd, fdpa, и тп. Впрочем, эту тему развивать не имеет смысла, так как выбирать особо не из чего. Ниже приведен список всех свободных «удобных» логинов, всего 84 штуки:

bfpm btxb bxpm dnta  dxkb dxkf dxna dxpn  fdtp fmtm fmxt fnpt  fnxp fpdm fpdx fpnf  ftxn kbpx kkdx kmdp  knxp knxt kpbf ktbp  ktbx ktpx kxpb mbxf  mfpx mpxf mtxp nbtd  nbtm ndxt nfbp nffp  nfpb nkbp nkdd nkdp  npbn npxt nxbk nxkf  nxkt pbfn pdtx pfnx  pfxn pmxf pnkd pxfk  pxpm pxtp pxxf tdxn  tfkx tkmm ttxk txbf  txkt txna txpb xbpf  xdnp xdpn xfbp xfpd  xfpn xfpt xkbf xkpn  xmbf xnnp xpbb xpkf  xpkt xpmf xpnp xptd  xtba xtdm xtdp xtkt

Можно отметить, что среди них есть также логины с повторяющимися буквами, что приближает их к трехсимвольным.

Зависимость между доступностью логина и числами, которые он содержит

Можно разбить логины на группы согласно числам, которые они содержат. Например, aa11 содержит одно число 11. Логин a0a1 содержит числа 0 и 1 и войдет в соответствующие этим числам группы. Отдельно будем учитывать номера с ведущими нулями вида 01. Всего таких групп будет 1 110.

В 894 из них ни один логин уже не доступен для регистрации. Можно найти свободные адреса для 107 трехзначных номеров (для большинства номеров остался только 1 логин из 26, максимум 3). Статистику по двухзначным номерам можно увидеть на диаграмме с комбинациями символов. Доступность логинов с числами от 0 до 10 визуально аналогична диаграмме с доступностью по отдельным символам.

Трехзначные номера, четырехсимвольные логины с которыми еще доступны

028 032 048 052 065 073  075 079 081 082 083 084  092 152 165 207 236 259  260 261 263 267 268 271  276 283 295 296 299 304  317 329 346 347 376 379  392 396 425 439 462 470  486 493 533 539 546 570  581 582 584 594 596 602  604 608 614 615 616 618  622 624 627 629 630 634  641 651 658 659 661 680  681 682 685 687 692 699  719 733 738 756 771 796  804 805 806 807 812 817  835 836 861 871 872 874  879 883 886 894 914 927  940 943 955 957 958

Группы занятых и свободных логинов, идущих подряд

Если отсортировать все логины в алфавитном порядке, то будет интересно посмотреть на группы непрерывно идущих друг за другом свободных и занятых адресов.

Количество таких групп примерно в 5.7 раз меньше, чем количество логинов. Самый большой непрерывный блок занятых логинов — 1 401 логин с fkzi по fm0e. Самая большая группа свободных логинов — 45 адресов с q6nf по q6on.

Напоследок отмечу, что отношение средних размеров свободных и занятых блоков равно отношению количества свободных и занятых логинов с точностью до 5 знака и составляет 0.20054

Заключение

Работая с этими данными стало даже интересно, насколько далеко можно зайти, анализируя таблицу, состоящую всего из двух столбцов (а по сути сводящуюся к списку из свободных логинов). Оказалось, что не так уж и далеко, но гораздо дальше, чем предполагалось в начале, когда планировалось узнать только долю свободных адресов.

ссылка на оригинал статьи https://habr.com/ru/articles/582816/

Выбираем логин на Яндекс.Почте

Подсчет количества логинов

Валидность и неразличимость

Общая формула

Генерация логинов и определение доступности

Результаты анализа доступности логинов

Зависимость между доступностью логина и его символами

Распределение логинов по форматам

Удобные логины

Зависимость между доступностью логина и числами, которые он содержит

Группы занятых и свободных логинов, идущих подряд

Заключение

Комментарии

Добавить комментарий Отменить ответ