Алфавитно-сортировочное
Dec. 20th, 2012 12:32 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
spamsinkДопустим, есть у нас набор слов. Поставим задачу научиться их сортировать. И даже, для простоты, допустим, что все эти слова используют один и тот же алфавит и мы должны научиться их сортировать согласно правилам конкретного языка на конкретный момент времени, глядя лишь на составляющие их алфавитные символы.
Оказывается, эта задача неразрешима без использования словаря или ручной правки подлежащего сортировке набора строк.
Есть такой датско-норвежский алфавит:
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.
Так что было бы желание, а добавление (возвращение) в русский алфавит каких-нибудь букв не будет ни беспрецедентным, ни сильно оторванным по времени от прецедентов изменения алфавитов языков с долгой историей.
Оказывается, эта задача неразрешима без использования словаря или ручной правки подлежащего сортировке набора строк.
Есть такой датско-норвежский алфавит:
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.
Так что было бы желание, а добавление (возвращение) в русский алфавит каких-нибудь букв не будет ни беспрецедентным, ни сильно оторванным по времени от прецедентов изменения алфавитов языков с долгой историей.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2012-12-20 09:23 pm (UTC)no subject
Date: 2012-12-20 09:38 pm (UTC)ФИО Дата Взнос
Иванов 11.12 12.20
Петров 12.11 11.99
no subject
Date: 2012-12-20 10:10 pm (UTC)Меня всегда удивляется нелогичная для меня система русских числительных в связи существительных: одна книга, два, три, четыре книги (род. пад., ед.ч.), пять книг. А почему не просто единственное число для одного и множественное число для большого чем одного. ) Но пример оффтоп немножко)
no subject
Date: 2012-12-20 10:20 pm (UTC)(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:no subject
Date: 2012-12-20 10:22 pm (UTC)Одна книга - ед. ч., именительный падеж
Две книги - мн. ч., именительный
Пять книг - мн. ч., родительный падеж
Но: Двадцать одна книга - опять единственное число! Хотя в английском, скажем, twenty one books.
(no subject)
From:(no subject)
From:(no subject)
From:no subject
Date: 2012-12-20 10:03 pm (UTC)В немецком я больше не помню, где ä, ö, ü. Но не после z, это я знаю.
no subject
Date: 2012-12-20 10:15 pm (UTC)1. Буква с диакритикой считается отдельной буквой со своим местом в алфавите.
2. Диакритика начинает играть роль в случае, если базовые буквы совпадают, и рассматривается слева направо (фр. coté < côte) или справа налево (кан. фр. côte < coté)
3. Диакритика перед сравнением расширяется в буквосочетание (напр. ä в ae).
Если мне память не изменяет, в немецком (по крайней мере в одной из стран, где немецкий - официальный) используется третий вариант.
no subject
Date: 2012-12-20 10:23 pm (UTC)Кстати, к отличию от Германии в Австртии нет фонетической разницы между "e" и "ä". :)
(no subject)
From:no subject
Date: 2012-12-21 08:44 am (UTC)(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:no subject
Date: 2012-12-20 10:15 pm (UTC)Разрешима или нет, в данном случае зависит от цели сортировки. Если это для обеспечения бинарного поиска, скажем, то зачем какие-то сложные правила, хватит положения символов в кодировке. То есть, или дискретное применение, или остальные применения настолько "гуманитарны"...
no subject
Date: 2012-12-20 10:16 pm (UTC)no subject
Date: 2012-12-20 10:25 pm (UTC)(no subject)
From:no subject
Date: 2012-12-20 11:51 pm (UTC)(no subject)
From:(no subject)
From:no subject
Date: 2012-12-21 01:03 am (UTC)no subject
Date: 2012-12-21 01:10 am (UTC)Но чем, собственно, toLowerCase так отличается от сортировки, что обязана быть независима от locale? Ведь вон, toUpperCase в одних языках оставляет диакритику, в других - убирает.
(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:кранты юниксу
From:no subject
Date: 2012-12-21 01:58 am (UTC)A Cellphone’s Missing Dot Kills Two People, Puts Three More in Jail
Разумеется, убивают людей не точки над i, а дикие нравы, но это уже другой вопрос.
(no subject)
From:(no subject)
From:(no subject)
From:no subject
Date: 2012-12-21 05:41 am (UTC)no subject
Date: 2012-12-21 05:46 am (UTC)проблемы локализации: Iı -İi
Date: 2012-12-21 07:25 am (UTC)no subject
Date: 2012-12-21 10:29 am (UTC)no subject
Date: 2012-12-21 04:35 pm (UTC)no subject
Date: 2012-12-21 05:46 pm (UTC)(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:no subject
Date: 2012-12-21 05:33 pm (UTC)Замечательные каталонцы
Date: 2012-12-28 10:57 am (UTC)Как там сортируют?
Инструменты
Date: 2012-12-28 11:45 am (UTC)Вот тут некоторые ругали филологов, а что такое INFINITY и NAN в свете сортировок?
И какие филологи писали IEEE 754?
А про путаницу с NULL в БД забыли?
А убивать надо тех, кто сортирову зашивает в бинарники. Это должно быть всегда доступно и пользователям, ибо программист в выходные спит, пока начальство внедряет творчество очередного взбесившегося принтера. А творчество ограничить невозможно.