?

Log in

No account? Create an account

Алфавитно-сортировочное - Общество дровосеков Бердичева по изучению Мишны

Dec. 20th, 2012

12:32 pm - Алфавитно-сортировочное

Previous Entry Share Next Entry

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

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



Есть такой датско-норвежский алфавит:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Æ Ø Å

В нем, как нетрудно видеть, буква Å (введенная вместо буквосочетания "aa" в норвежском в 1917 г., а в датском - в 1948 г., с окончательной фиксацией позиции в алфавите в 1955 г.) сортируется после буквы Z. Это несложно поддержать алгоритмически.

В отличие от норвежского, в датском языке в именах собственных, включая местные географические названия, новая буква не используется, а пишется Aa, но в целях сортировки диграф рассматривается как атомарная буква Å. Поэтому, например, в алфавитном списке городов мира датский город Aabenraa будет идти после города Zagreb. Это тоже несложно поддержать алгоритмически.

Но! В именах собственных не-скандинавского происхождения Aa рассматривается, как две отдельные буквы A, поэтому правильный алфавитный порядок для городов Aabenraa, Aachen, Zagreb таков: Aachen, Zagreb, Aabenraa. Для автоматизации такой сортировки между буквами, которые должны рассматриваться по отдельности, а не как диграф, вставляется символ U+034F с неочевидным названием COMBINING GRAPHEME JOINER, ведь он ничего не соединяет, а даже наоборот. Правильнее было бы назвать его DIGRAPH SEPARATOR, но уже поздно.

И на закуску: до 1980 г. в датском языке буква W считалась графическим вариантом буквы V, поэтому лексикографический порядок был такой, например: Wales, Vallø, Washington, Wedellsborg, Vendsyssel (представьте себе что-нибудь подобное в русском: "шапка, щётка, щука, шутка").
В 1980 г. стали считать V и W отдельными буквами, но упоминаемое в детской алфавитной песенке количество букв осталось прежним - 28, а не 29.

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

Comments:

[User Picture]
From:sab123
Date:December 20th, 2012 09:23 pm (UTC)
(Link)
Одно слово, филологи!
(Reply) (Thread)
[User Picture]
From:occam_aga
Date:December 20th, 2012 09:38 pm (UTC)
(Link)
бухгалтеры не лучше :)

ФИО Дата Взнос
Иванов 11.12 12.20
Петров 12.11 11.99
(Reply) (Parent) (Thread)
[User Picture]
From:komar28
Date:December 20th, 2012 10:10 pm (UTC)
(Link)
:) ну, логика есть. То есть, то, что логично в одном языке или для носителей одного языка, кажется нелогичным в другом или для носителей другого.

Меня всегда удивляется нелогичная для меня система русских числительных в связи существительных: одна книга, два, три, четыре книги (род. пад., ед.ч.), пять книг. А почему не просто единственное число для одного и множественное число для большого чем одного. ) Но пример оффтоп немножко)
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:komar28
Date:December 20th, 2012 10:03 pm (UTC)
(Link)
Это интересно, про Aachen понятно, это просто длинное гласное, но не-скандинавски, хотя я не знаю, как город произносится в Дании или Норвегии.

В немецком я больше не помню, где ä, ö, ü. Но не после z, это я знаю.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:December 20th, 2012 10:15 pm (UTC)
(Link)
Вариантов сортировки диакритики бывает три (с половиной):

1. Буква с диакритикой считается отдельной буквой со своим местом в алфавите.
2. Диакритика начинает играть роль в случае, если базовые буквы совпадают, и рассматривается слева направо (фр. coté < côte) или справа налево (кан. фр. côte < coté)
3. Диакритика перед сравнением расширяется в буквосочетание (напр. ä в ae).

Если мне память не изменяет, в немецком (по крайней мере в одной из стран, где немецкий - официальный) используется третий вариант.
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:fatoff
Date:December 20th, 2012 10:15 pm (UTC)
(Link)
> Оказывается, эта задача неразрешима без использования словаря или ручной правки подлежащего сортировке набора строк.

Разрешима или нет, в данном случае зависит от цели сортировки. Если это для обеспечения бинарного поиска, скажем, то зачем какие-то сложные правила, хватит положения символов в кодировке. То есть, или дискретное применение, или остальные применения настолько "гуманитарны"...
(Reply) (Thread)
[User Picture]
From:spamsink
Date:December 20th, 2012 10:16 pm (UTC)
(Link)
Допустим, цель сортировки - показать список имен файлов в каталоге в лексикографическом порядке. Не такое уж гуманитарное применение.
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:fatoff
Date:December 20th, 2012 10:25 pm (UTC)
(Link)
Ну, это 'показать' уже UI, слегка гуманитарное... Надо ещё одну таблицу для трансляции алфавита... знаю пару датчан, надо поинтересоваться, как их заденет постановка 'aa' после 'z'. Ответ знаю. :-)
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:juan_gandhi
Date:December 21st, 2012 01:03 am (UTC)
(Link)
Добавим сюда турецкую букву I, ломающую всю международную систему toLowerCase...
(Reply) (Thread)
[User Picture]
From:spamsink
Date:December 21st, 2012 01:10 am (UTC)
(Link)
Я думал об подобном: http://linguaphiles.livejournal.com/2725148.html

Но чем, собственно, toLowerCase так отличается от сортировки, что обязана быть независима от locale? Ведь вон, toUpperCase в одних языках оставляет диакритику, в других - убирает.



(Reply) (Parent) (Thread)
[User Picture]
From:yatur
Date:December 21st, 2012 01:54 am (UTC)
(Link)
Там был epic fail с системными файлами типа win.ini. Код Виндоуз был написан в святой уверенности, что "win.ini" и "WIN.INI" это один и тот же файл. А по турецким правилам получалось, что пары должны быть либо win.ini/WİN.İNİ, либо wın.ını/WIN.INI. Я так сходу даже не найду в какой версии от этого избавились.
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:stas
Date:December 21st, 2012 02:16 am (UTC)
(Link)
Это кошмар, когда в турецкой локали старый добрый сишный tolower() начинает нести ерунду и надо писать собственный вариант, но применять его не везде - потому что кое-где турки всё-таки хотят свои национальные правила. Ладно бы он делал это с какими-нибудь страшными умляутами - но когда strtolower("INIT") становится не то же самое, что "init", то гемора резко становится очень много.
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:yatur
Date:December 21st, 2012 01:58 am (UTC)
(Link)
Вот, кстати, что нагуглилось: http://gizmodo.com/382026/a-cellphones-missing-dot-kills-two-people-puts-three-more-in-jail

A Cellphone’s Missing Dot Kills Two People, Puts Three More in Jail

Разумеется, убивают людей не точки над i, а дикие нравы, но это уже другой вопрос.
(Reply) (Parent) (Thread)
[User Picture]
From:spectat
Date:December 21st, 2012 05:40 am (UTC)
(Link)
интересная история...
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:December 21st, 2012 09:33 am (UTC)
(Link)
Да, помню, пробегало в рассылках.
(Reply) (Parent) (Thread)
[User Picture]
From:alon_68
Date:December 21st, 2012 05:41 pm (UTC)
(Link)
Там последняя фраза отдельно доставляет.
(Reply) (Parent) (Thread)
[User Picture]
From:spectat
Date:December 21st, 2012 05:41 am (UTC)
(Link)
интересно, а как в языках с иерографическим письмом делают сортировку?
(Reply) (Thread)
[User Picture]
From:stas
Date:December 21st, 2012 05:46 am (UTC)
(Link)
Вот например: http://blogs.msdn.com/b/michkap/archive/2006/01/03/508579.aspx
(Reply) (Parent) (Thread)
[User Picture]
From:livejournal
Date:December 21st, 2012 07:25 am (UTC)

проблемы локализации: Iı -İi

(Link)
User spectat referenced to your post from проблемы локализации: Iı -İi saying: [...] Hamlet demişkən, olummu, ölümmü, sual budur, bu. ссылку увидел в комментарии к посту [...]
(Reply) (Thread)
[User Picture]
From:Anatoly Borodin
Date:December 21st, 2012 10:29 am (UTC)
(Link)
В венгерском тоже весело http://en.wikipedia.org/wiki/Hungarian_alphabet#Alphabetical_ordering_.28collation.29 ()
(Reply) (Thread)
[User Picture]
From:spamsink
Date:December 21st, 2012 04:35 pm (UTC)
(Link)
Geminates of multigraphs - прелесть!
(Reply) (Parent) (Thread)
[User Picture]
From:alon_68
Date:December 21st, 2012 05:46 pm (UTC)
(Link)
В общем, некоторым языкам пора делать очередную алфавитную реформу в связи с изменившимися обстоятельствами.
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:alon_68
Date:December 21st, 2012 05:33 pm (UTC)
(Link)
В каталонском существует вполне визуальный сепаратор в виде точки в середине - Llobregat Льобрегат, но paral·lel параллель.
(Reply) (Thread)
[User Picture]
From:andybil
Date:December 28th, 2012 10:57 am (UTC)

Замечательные каталонцы

(Link)
А знатоков китайского тут нет?
Как там сортируют?
(Reply) (Parent) (Thread)
[User Picture]
From:andybil
Date:December 28th, 2012 11:45 am (UTC)

Инструменты

(Link)
Ну понятно же уже, что нужен инструмент, который позволит изменять порядок сортировки на любые алфавиты.
Вот тут некоторые ругали филологов, а что такое INFINITY и NAN в свете сортировок?
И какие филологи писали IEEE 754?
А про путаницу с NULL в БД забыли?
А убивать надо тех, кто сортирову зашивает в бинарники. Это должно быть всегда доступно и пользователям, ибо программист в выходные спит, пока начальство внедряет творчество очередного взбесившегося принтера. А творчество ограничить невозможно.
(Reply) (Thread)