Творческий отбор

Если вы хотели написать слово cold (холодный), но напечатали colf, вы можете представить себе, как четвертый рычажок «переключается» на другую букву, чтобы получилось желаемое слово. Основная идея, стоящая за автоисправлением, — это поиск лучшей комбинации букв с учетом нажатых клавиш и оценка букв, находящихся по соседству с ними. Поскольку в раскладке QWERTY D находится около F, программа может автоматически исправить colf на cold.

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

• Распределить нажатые клавиши в ряд переключений с соседними буквами.

• Прокрутить рычажки, чтобы проверить каждую комбинацию букв.

• Отметить в словаре слова, найденные при прокручивании рычажков.

• Предложить найденное слово с самым высоким значением частоты использования.

Первоначально я разработал этот алгоритм для моей победившей в дерби клавиатуры, и он хорошо себя показал, когда на каждую клавишу приходилось по несколько букв. Также он был хорошим решением, когда все мы в команде Purple только начинали осваивать печать на сенсорном экране. Месяцы спустя, когда клавиатура QWERTY с одной буквой на каждой клавише заменила прошлую и все стали делать гораздо больше ошибок в каждом слове, поскольку клавиши значительно уменьшились, простого подхода с переключателями было уже недостаточно. Он мог надежно заменить одну неверную букву в широко употребительном слове, как в моем примере с colf и cold, но гораздо хуже показывал себя, если вы печатали что-то вроде vild, так как не мог понять, что вы хотели написать — cold, bold (жирный) или vile (подлый). У меня не было хороших идей, как ответить на этот вопрос, а также хороших идей по улучшению моего кода «велосипедного замка». Я отправился на поиски помощи.

Попросить о помощи было непросто в другом смысле. Я узнал имена нескольких людей в Apple, которые имели опыт в создании словарей и алгоритмов ввода текста, но они не участвовали в проекте Purple и не было никакого способа посвятить их в большую тайну смартфона.

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

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

Но это не оказалось таким огромным препятствием, каким могло бы стать. Эксперты по текстам Apple, кажется, совершенно не были обижены моей вынужденной конфиденциальностью в стиле шпионских романов. Они рассказали мне о таких понятиях, как цепи Маркова, условных случайных полях, Байесовских выводах и динамическом программировании.

В конце концов, эти технические разговоры больше вдохновили меня, чем напрямую повлияли на мои алгоритмы. Честно говоря, бо́льшая часть подобной математики была мне недоступна. У меня нет инженерной подготовки — на самом деле, в колледже я не взял ни одного математического курса. Если когда-либо и был какой-то довод в пользу того, чтобы продолжать изучение этого предмета после окончания старшей школы (ведь никто не говорил мне, что математика может мне понадобиться), то это был как раз он. Я пытался прыгнуть выше своей головы.

Тем не менее я не совсем растерялся. Когда Ричард Уильямсон пришел в Apple и помог нам определиться с техническим направлением нашего проекта по созданию браузера, он показал, что можно совершить технический прорыв, временно пропуская проблемы, которые не можешь решить, в пользу тех, для которых у тебя есть решение. Именно это я и сделал.

Я начал с того, что представил свою клавиатуру QWERTY с одной буквой на каждой клавише и сделал предположение о том, каким образом я могу ошибиться с клавишей, на которую нацеливаюсь.

Я предположил, что, если я хочу нажать клавишу G, но палец попадает налево и нажимает на F, с большей вероятностью я имею в виду G или F, а не H. Другими словами, если я попадаю по клавише, в которую не целился, то та, которую я намеревался нажать, скорее всего, будет следующей ближайшей к ней. Я встроил направление этих пропусков в свой алгоритм.