BogdanPetrov 11 окт 2021 в 16:50

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

7 мин

27K

Много лет назад я зарегистрировал себе несколько трех- и четырехсимвольных адресов на Яндекс.Почте. Они оказались очень удобными, потому что их легко писать и диктовать, особенно вместе с доменом 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,m \in \mathbb{Z}, \\ n > 0, \\ 0 \leqslant m \leqslant \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

Заключение

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

Теги:

Хабы:

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

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

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

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

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

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

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

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

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

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

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

Заключение

Публикации

Истории

Работа

Ближайшие события