Пользователь
0,0
рейтинг
27 января 2012 в 01:15

Разработка → Обычная (или не совсем обычная) транслитерация на Python

Как-то раз возникла необходимость написать транслитерацию на Python — из кириллицы в латиницу. Из слова «ситх» получается «sith», а из «шелест» выходит «shelest».

Казалось бы, чего тут вообще писать — задача едва сложнее print "Hello world". И это отчасти так — но не совсем.

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

Но, поскольку правила транслитерации мы менять точно не собираемся, то посмотрим, что получится при использовании обычной транслитерации.

К примеру, фраза «ШАПКА и Юля» преобразуется в «SHAPKA и YUlya», либо в «ShAPKA и Yulya» — в зависимости от того, что задано в таблице транслитерации для «Ш» и «Ю» (иногда задаётся «SH» и «YU», а иногда «Sh» и «Yu»).

То есть регистр следующей буквы в стандартных функциях транслитерации не учитывается, и все буквы в верхнем регистре заменяются по общим правилам. Поэтому в ходе транслитерации для слов «ЧАША» и «Щи» легко получается что-то вроде «ChAShA» или «SCHi», когда реально мы скорее хотели получить «CHASHA» и «Schi».

Тем не менее, все найденные реализации транслитерации из кириллицы в латиницу на Python, как выяснилось, эту особенность не учитывали. Это и многочисленные решения, приведённые на форумах, и библиотека pytils, реализующая транслитерацию в одном из своих модулей.

Значит, напишем свою функцию транслитерации, с блэкджеком и^W^W^W^H^H. :)


Итак, первый вариант — пройтись по строке посимвольно. В этом случае всегда известно, какой символ следующий (если это не последний символ в строке).

Принцип такой:

  1. Для каждого символа проверяется, есть ли он среди ключей словаря lower_case_letters.
  2. Если есть, то он заменяется на значение для данного ключа в lower_case_letters.
  3. Если нет, то проверяется, есть ли этот символ среди ключей словаря capital_letters.
  4. Если есть, то проверяется, последний ли это символ в строке (если длина строки больше, чем позиция текущего символа + 1 — значит, это ещё не последний символ, при условии, что позиция отсчитывается от нуля).
  5. Если символ не последний, то проверяется, есть ли следующий символ среди ключей словаря lower_case_letters.
  6. Если нет, либо если это последний символ в строке, то текущий символ заменяется на значение для данного ключа в словаре capital_letters, при этом для значения применяется метод upper() — то есть из «Sh» получается «SH», и так далее.
  7. Если же следующий символ есть среди ключей словаря lower_case_letters — то метод upper() не применяется.

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

Для большей точности время выполнения (и на этом, и на другом графике) указано не для одной операции транслитерации, а для 500. Процессор, установленный на компьютере — Intel Core 2 Quad CPU Q9400 @ 2.66GHz.

График

Что ж, стало очевидно, что для более быстрой обработки длинных строк нужно как-то использовать замену каждого отдельного символа сразу по всей строке (replace). А по сути, заменяться же может и не один символ, а сразу группа символов. Так и появился второй вариант.

Вообще, надо сказать, что замена групп символов — не единственное решение, которое приходило в голову. Сначала, например, возникла идея делить строку на слова, затем для каждого слова проверять регистр (если слово, в котором все символы переводятся в верхний регистр, равно первоначальному слову, значит, такое слово целиком в верхнем регистре), и, если слово написано в верхнем регистре, то применять отдельную таблицу транслитерации, специально для слов в верхнем регистре. Соответственно, в этом случае буква «Ш» в слове «Шахматы» будет транслитерирована как «Sh», а вот в слове «ШАХМАТЫ» уже как «SH».

Правда, в словах, написанных в смешанном регистре (например, «ШАХматЫ») будет в любом случае использована обычная таблица транслитерации (то есть, получится ShAHmatY). Но это уже, в общем-то, не так важно.

Либо, как вариант, можно было бы сделать ещё более универсально — применять replace для слов, написанных в нижнем регистре, а остальные слова обрабатывать посимвольно. Но это уже, вероятно, было бы медленнее, потому что таких слов, скорее всего, получится много.

Тем не менее, вернёмся ко второму написанному варианту. Принцип у него заключается в том, чтобы выделить те русские буквы, которые представляются в виде сразу нескольких латинских символов, в отдельный словарь, после чего по циклу создать словарь (таблицу транслитерации) из пар символов, где для каждой из таких букв (Ж, Ц, Ч, Ш, Щ, Ю и Я) есть 33 разных варианта, с каждой из строчных букв русского алфавита. Соответственно, остаётся сначала сделать замену для таких пар символов, а затем для всех остальных символов, которые остались не транслитерированы.

Но именно такой вариант оказался очень медленным (на самом деле медленной оказалась реализация — но об этом ниже).

Если говорить более точно, то он быстрее первого варианта только при очень большом количестве символов — около 10 тысяч.

А при обработке строк от 100 до 1000 символов первый вариант оказывается приблизительно в 10 раз быстрее.

Что ж, 7 * 33 = 231. То есть 231 дополнительная замена. Конечно, в словаре мы не встретим многих из этих сочетаний букв — то есть, теоретически, можно было бы сделать и меньшее количество операций замены. Но, с другой стороны, текст может состоять не только из слов, которые есть в словаре, да и вообще лишний раз вносить подобные ограничения не хочется.

На самом деле, как оказалось, дело не в том, что производится большое количество операций замены, а в том, как именно реализована замена символов (смотри четвёртый вариант).

Впрочем, сначала рассмотрим третий вариант.

Третий вариант чем-то похож на второй, но тут уже нет 231 отдельной замены для каждой возможной комбинации Ж, Ц, Ч, Ш, Щ, Ю и Я со строчными буквами. Вместо этого там используется регулярное выражение, которое применяется всего для 7 замен. Каждая из букв, соответствующих нескольким латинским буквам, после которой следует строчный символ ([а-я]) заменяется на латинское представление данной буквы, после которого следует тот же строчный символ (без транслитерации). После этого, соответственно, оставшиеся строчные буквы заменяются отдельно, как, впрочем, и прописные. При замене прописных букв, соответствующих нескольким латинским символам, для латинского представления буквы применяется метод upper().

И вот этот вариант уже как раз оказался очень быстрым по сравнению со вторым.

На строках в 100 символов он, надо отметить, медленнее, чем первый вариант. А вот на строке в 1000 символов он уже в два раза быстрее первого варианта, и в 19,5 раз быстрее второго.

В принципе, на этом можно бы было закончить, но реально есть ещё кое-что, что можно и нужно добавить.

Если написать import this, то мы получаем всем известный текст, дзэн языка Python. Помимо прочего, там есть фраза о том, что «должен быть один — и, желательно, только один — очевидный способ сделать это». Однако любой, кто достаточно долго программировал на Python, знает о том, что нередки случаи, когда есть довольно много способов сделать одно и то же, и при использовании любого из них результат может быть абсолютно одинаковым, но время, затрачиваемое на выполнение операции, может отличаться очень сильно.

Так, например u"Ваше имя — %s" % username выполняется намного быстрее, чем u"Ваше имя — "+username. Об этом хорошо и подробно написано в статье «Efficient String Concatenation in Python».

Аналогично и здесь — строку можно заменить через re.sub, а можно воспользоваться строковым методом replace. Причём если при какой-либо замене не используются регулярные выражения, то настоятельно рекомендуется пользоваться именно вторым способом, который, к тому же, работает намного быстрее. Кстати, в том же pytils используется именно строковой метод replace.

Итак, четвёртый вариант (второй вариант с правками). Отредактированы всего три строчки, но производительность увеличилась колоссально.

Этот вариант лучше всех остальных при строках в 1000 и в 10000 символов. На строках в 100 символов разница по сравнению с тем, что было (второй вариант), тоже очень велика.

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

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

Без сомнения, это должно было сильно повлиять на производительность: скорость у пятого варианта получилась в среднем в 1,5 раза больше, чем у третьего. Причём оказалось, что на строке в 100 символов пятый вариант работает даже быстрее первого (то есть быстрее посимвольной обработки).

График

Получается, что алгоритмы с заменой оказались быстрее, чем посимвольная обработка, для строк в 100, 1000 и 10000 символов.

И всё же у каждого варианта есть свои достоинства и недостатки. К примеру, даже несмотря на то, что в пятом варианте строка в 100 символов обрабатывается быстрее, чем с помощью посимвольного прохождения по строке, на совсем маленьких строках (в несколько символов — а бывает и такое) посимвольная обработка всё равно окажется самым быстрым вариантом.

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

В завершение хочу привести цитату Майка Хертеля (Mike Haertel — автор GNU Grep) из его сообщения в списке рассылки freebsd-current относительно того, почему GNU Grep работает настолько быстро:

The key to making programs fast is to make them do practically nothing. ;-)

«Ключ к тому, чтобы сделать программы быстрыми — добиться, чтобы они практически ничего не делали».

Если есть ещё какие-то мысли — смело дописывайте, дополняйте. Если появятся ещё какие-то доработки, думаю, для многих это может быть интересно.
Арсений @MaGIc2laNTern
карма
231,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (31)

  • +1
    Еще есть format у str и нужно вариант модуля на Си.
  • +1
    Такой вариант протестируйте пожалуйста: gist.github.com/1685623
    • +2
      Спасибо за вариант! :)

      Протестировал.

      100 символов: 0.085 секунд
      1000 символов: 0.752 секунд
      10000 символов: 7.321 секунд

      Тест точно такой же — время выполнения 500 одинаковых операций.

      Поскольку ваш вариант оказался самым крутым при обработке 100 символов — решил ради интереса сравнить его с первым вариантом на очень маленькой строке («Юный химик» — 10 символов).

      Но тут первый вариант всё же оказался быстрее — всего 0.001 секунд. Ваш вариант занял 0.016 секунд.
  • +1
    Сохранение регистра букв надо, только если вы потом захотите обратно преобразовать транслит в кирилицу. Но при этом вы наступите еще на пару граблей, потому что, опять-таки, преобразование не 1 к 1.

    А в остальных 99.99% случаев транслитерация букв нужна для получения ascii-идентификаторов. Ключей в базе, урлов (тут сомнительно, потому что нормальный юникод давно везде работает). А исходя из сути идентификаторов — нам начхать на регистр. Более того, в половине из этих случаев стоит приводить все к одному регистру, потому что есть еще подводные камни, связанные с сортировкой (двоичной, а не символьной).
    • 0
      Есть ещё одно применение — преобразование текста (названий и прочего) в латиницу с целью обеспечить возможность чтения нерусскоговорящими людьми.

      Разумеется, прочитают они это всё равно не вполне корректно, но вот отсутствие подобного прыгающего регистра в транслитерации (там, где реально было обычное слово с большой буквы или слово целиком в верхнем регистре) может помочь чтению.
      • –2
        А такое бывает? По-моему, изучение любого языка начинается с алфавита.

        Ну, разве что таблички в туристических местах, с текстами типа «Tsentralnaya ploschad». Но оно вырвиглазное по своей сути (кто им мешает нормально перевести название? нигде такого бреда не встречал, кроме как в бывшем союзе), во первых, во вторых, тут нет объемов (если уж бенчмарки затеяли, значит объемы принципиальные), в третьих — ручная правка текста будет все-равно.
        • +1
          Ну, как сказать.

          Если даже вы, не зная русского, спросите:
          Excuse me, where is the Tsentralnaya ploschad?
          То вам, скорее всего, покажут пальцем, куда идти.
          А вот если вы спросите:
          Where is the Central Square?
          То велика вероятность, что тот, у кого вы будете спрашивать, не поймёт вообще ничего. Можете даже проэкспериментировать как-нибудь ради интереса. Незнание английского языка — совершенно типичное явление в любой неанглоговорящей стране. Тут, в общем-то, нечему удивляться. По этой причине транслит во многих случаях лучше, чем перевод. Иногда, кстати, встречается и то, и другое рядом, когда название дублируется в транслите и в переводе.
          • 0
            А между собой они будут «what the fuck is tsentralnaya ploschad?». И будут искать какой-нить памятник, скамейку, бабУшку, в конце концов, но так и не узнают, что это всего лишь central square.

            > Можете даже проэкспериментировать как-нибудь ради интереса.

            Сталкивался. Не понимают точно так же, как и «where is central square?».

            > Незнание английского языка — совершенно типичное явление в любой неанглоговорящей стране.

            Бывший союз, скорее. В остальном мире как-то с этим по-лучше.
            • +2
              В Испании тоже основные массы плохо знают английский. Впрочем, говорят, и англичан они сильно не любят.
            • 0
              > А между собой они будут «what the fuck is

              Чем-то напоминает Задорнова «ну тупыеее». Правда это мало соотносится с действительностью: англоговорящие не испытывают таких проблем с иностранными названиями, как Вы хотите это преподнести, для них вполне нормальны подобные вкрапления иностранных названий

              «Notre Dame Cathedral (full name: Cathédrale Notre-Dame de Paris, „Our Lady of Paris“) is a beautiful cathedral on the the Île de la Cité in Paris»


              Что также добавляет и своеобразный шарм экзотики — каждая страна звучит по своему, а не везде одинаковые названия, как было бы, если б всё переводилось. Разумеется, узнать перевод, как в примере, — тоже интересно, но этого достаточно один раз.
  • +2
    Если вам нужно заменить символы одного алфавита на соответствующие им символы другого алфавита. можно обойтись и без циклов, и без регулярок. Есть же string.translate и его верный друг string.maketrans.

    Для замен, в которых участвую строки длиннее одного символа все-так понадобится цикл. Но таких замен сильно меньше односимвольных.
  • 0
    А вообще, если вы так гонитесь за скоростью, перепишите первый вариант на sed, по скорости это решение порвет 99% других (на любом языке), а по соотношению (скорость) / (скорость разработки) — так и все 100%.
  • 0
    Neuželi tak složno ne translitizirovat' kirillicu, a romanizirovat' jejo v samuju obyčnuju latinicu s diakritikoj? Eto že tak prosto!
    • +4
      А почему у вас 'ю' транслитерировалось в 'ju', 'е' в 'je' и 'ё' в 'jo', если это так просто? :)
    • +1
      Даже в вашем примере есть «je» и «jo» — то есть опять же, некоторые буквы транслитерируются (романизируются) не в одну, а в несколько латинских букв.

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

      Можно было бы, конечно, добиться и того, чтобы любая буква была представлена как одна латинская (с добавлением диакритических знаков или в виде лигатур), но в итоге тем, кто это читает, пришлось бы выучить правила чтения этих символов. А если уж учить новые символы, то там и до того, чтобы просто выучить кириллицу, недалеко.
    • +2
      Напишите-ка мне букву «щ»? :)
      • +1
        чёрт, так надеялся, что не вспомнят :) но можно ввести польскую: ś
        вариантов — море! главное только — стандартизировать и всё
    • +1
      В ASCII не поместится.
    • 0
      Хм, Neu%C5%BEeli%20tak%20slo%C5%BEno?
  • 0
    100мс как-то много для строки из одного символа.
    Это время выполнения функции уже в стартоаввшей программы весь запуск программы?
    • 0
      Вы правы. Сейчас перепроверил — получилось всё-таки 0.01 (это вся программа — в данном случае ещё и с выводом результата на экран все 500 раз).

      2526 function calls in 0.010 CPU seconds

      Из этого функиця transliterate:

      test.py:3(transliterate)
      ncalls: 500
      tottime: 0.006
      percall: 0.000
      cumtime: 0.006
      percall: 0.000
    • 0
      Обновил график.

      (Старый график: chart_1.png.)
      • 0
        Кстати, если сравнить два графика, то видно, что у них отличаются и другие значения. Это связано с тем, что использовались разные шаблоны строк. То есть скопированная n раз последовательность символов «Шахматы» обрабатывается за одно время, а последовательность «Юный химик», с помощью которой была получена строка той же длины, обрабатывается за другое время.
  • 0
    Помню писал такую утилиту, чтобы русские названия треков в плеере крякозяброй не высвечивались. Заморочки с заглавными буквами мне и в голову тогда не пришли, потому и программа была не сложнее «Hello world».
  • +1
    Частично справляется вот эта мегауниверсальная штука:
    >>> import unidecode
    >>> unidecode.unidecode(u'ШШШ Щячло')
    'ShShSh Shchiachlo'
    
    • 0
      Класс, спасибо.

      Да, в части случаев это отлично подойдёт. :)
    • 0
      еее, то что доктор прописал! спасибо, бро!
  • 0
    Посмотри вот на это: pypi.python.org/pypi/trans
    Давно я его написал… На скорость не ориентировался, но это реально надо?
  • +1
    Я бы плюсанул, но кармы нет, поэтому просто спасибо. Именно сегодня этот пост сэкономил мне много нервов.
  • +1
    А вы смотрели unidecode? У меня правда был другой критерий отбора, чтобы переводила в транслит любой набор символов на любом языке.
    • 0
      На момент написания статьи — не смотрел, конечно: библиотека на PyPI с 20 сентября 2013, а эта статья опубликована 27 января 2012.

      Сейчас посмотрел. В текущей версии у неё та же самая проблема с заглавными буквами, что и у почти всех других реализаций, которые можно найти в Интернете:

      >>> unidecode(u"США")
      'SShA'
      

      А в остальном — хорошая библиотека. Для создавния slug (которые всё равно переводятся в нижний регистр) самое то.

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