Jak sortować alfabetycznie ciągi znaków Unicode w Pythonie?


98

Python domyślnie sortuje według wartości bajtów, co oznacza, że ​​é występuje po z i innych równie zabawnych rzeczach. Jaki jest najlepszy sposób sortowania alfabetycznego w Pythonie?

Czy jest do tego biblioteka? Nic nie mogłem znaleźć. Najlepiej, jeśli sortowanie powinno mieć obsługę języka, aby rozumieć, że åäö powinno być sortowane po szwedzku po z, ale ü powinno być sortowane według u, itd. Dlatego obsługa Unicode jest w dużym stopniu wymagana.

Jeśli nie ma do tego biblioteki, jaki jest najlepszy sposób, aby to zrobić? Po prostu wykonaj mapowanie z litery na wartość całkowitą i zamapuj ciąg na listę liczb całkowitych za pomocą tego?


11
Zwróć uwagę, że jest to jeszcze bardziej zależne od lokalizacji: w szwedzkim (jak podasz) „Ę” występuje po „Z”, ale w języku niemieckim „Ę” jest zwykle sortowane jako „AE”.
balpha

@Georg: Czy był powód, dla którego otworzyłeś za to nagrodę? locale.strcollOdpowiedź jest poprawna, kiedy trzeba Unicode sortowania za pomocą ustawień regionalnych użytkownika, a odpowiedź ICU co chcesz i kiedy trzeba więcej niż (sortowanie przy użyciu więcej niż jednego regionu). W większości przypadków chcesz locale.strcoll.
Glenn Maynard,

@Glenn: Chciałem wiedzieć, jak dobrze locale.strcolldziała, a zwłaszcza co ICU robi lepiej niż funkcja Pythona. Zasadniczo trochę więcej uwagi na pytanie.
Georg Schölly,

1
@Georg: Ostatnio dużo bawiłem się algorytmem sortowania Unicode, jak widać po mojej odpowiedzi. Naprawdę wspaniale jest móc na przykład sortować, --locale=de__phonebookkiedy tego potrzebujesz. Moduł Perl przechodzi zestaw testów UCA, a skrypt, który dostarczyłem , znacznie ułatwia grę z całym UCA i wszystkimi jego opcjami, w tym ustawieniami narodowymi, tylko z wiersza poleceń. Może nie odpowiedzieć na pytanie, ale powinno być bardzo interesujące. Jeśli jesteś w Szwajcarii, jestem pewien, że możesz skorzystać z elastyczności. :)
tchrist

Odpowiedzi:


75

Robi to biblioteka IBM ICU (i wiele więcej). Posiada powiązania Pythona: PyICU .

Aktualizacja : Podstawowa różnica w sortowaniu między jednostkami ICU locale.strcollpolega na tym, że ICU używa pełnego algorytmu sortowania Unicode, podczas gdy strcollużywa ISO 14651 .

Różnice między tymi dwoma algorytmami zostały pokrótce podsumowane tutaj: http://unicode.org/faq/collation.html#13 . Są to raczej egzotyczne przypadki szczególne, które w praktyce rzadko mają znaczenie.

>>> import icu # pip install PyICU
>>> sorted(['a','b','c','ä'])
['a', 'b', 'c', 'ä']
>>> collator = icu.Collator.createInstance(icu.Locale('de_DE.UTF-8'))
>>> sorted(['a','b','c','ä'], key=collator.getSortKey)
['a', 'ä', 'b', 'c']

Czy to działa tak samo w Pythonie 2 i Pythonie 3? Skorzystałem locale.strxfrmz odpowiedzi u0b34a0f6ae i wydaje się, że działa i jest znacznie bardziej elegancki i nie wymaga żadnego dodatkowego oprogramowania.
sup.

Nie działa z Python3 dla mnie, sudo pip3 install PyICUnie można zainstalować, podobnie jak w przypadku Python2.
imrek

Musiałem zainstalować libicu-devel.x86_64, aby pyICU mógł skompilować i zainstalować z Pipa. Działa, chociaż wynik ostatniego polecenia „posortowanego” to: ['a', '\ xc3 \ xa4', 'b', 'c']
Mike Stoddart

53

Nie widzę tego w odpowiedziach. Moja aplikacja sortuje według ustawień regionalnych przy użyciu standardowej biblioteki Pythona. To całkiem proste.

# python2.5 code below
# corpus is our unicode() strings collection as a list
corpus = [u"Art", u"Älg", u"Ved", u"Wasa"]

import locale
# this reads the environment and inits the right locale
locale.setlocale(locale.LC_ALL, "")
# alternatively, (but it's bad to hardcode)
# locale.setlocale(locale.LC_ALL, "sv_SE.UTF-8")

corpus.sort(cmp=locale.strcoll)

# in python2.x, locale.strxfrm is broken and does not work for unicode strings
# in python3.x however:
# corpus.sort(key=locale.strxfrm)

Pytanie do Lennarta i innych osób odpowiadających: Czy nikt nie zna „lokalizacji”, czy też nie spełnia tego zadania?


Przy okazji 1) Nie sądzę, żeby locale.strxfrm było uszkodzone dla `str 'zakodowanego w UTF-8; Przeprowadziłem test porównawczy przez aplikację i doszedłem do wniosku, że użycie cmp = strcoll na obiektach Unicode jest tańsze niż dekodowanie wszystkiego do UTF-8 i użycie klucza = strxfrm
u0b34a0f6ae

6
Przy okazji 2) Moduł locale będzie działał tylko z wygenerowanymi przez ciebie lokalizacjami (dla Linuksa), a nie z dowolnymi ustawieniami narodowymi. „locale -a” powie ci, które
u0b34a0f6ae

6
@Georg: Uważam, że locale obsługuje tylko proste mapowanie podciągów-> collating_element. Nie obsługuje takich rzeczy, jak rozszerzenia (æ posortowane jako „ae”), sortowanie francuskiego akcentu (litery od lewej do prawej, ale akcenty od prawej do lewej), przegrupowanie i prawdopodobnie kilka innych. Szczegóły tutaj (pełny zestaw funkcji UCA): unicode.org/reports/tr10 i tutaj (zestawienie regionalne): chm.tu-dresden.de/edv/manuals/aix/files/aixfiles/LC_COLLATE.htm
Rafał Dowgird

2
Aby jasno odpowiedzieć na pytanie: tak, to zadanie. Najwyraźniej istnieją specjalne przypadki, w których pełny algorytm sortowania Unicode radzi sobie lepiej, ale chyba że już wiesz, że są szanse, że nie zauważysz.
Lennart Regebro,

1
Największym problemem jest to, że musisz ustawić locale globalnie dla całej aplikacji. - Nie możesz tego mieć pod ręką tylko do porównania.
Robert Siemer,

9

Wypróbuj algorytm sortowania w formacie Python Unicode Jamesa Taubera . Może nie działać dokładnie tak, jak chcesz, ale wydaje się, że warto go zobaczyć. Aby uzyskać więcej informacji na temat problemów, zobacz ten post autorstwa Christophera Lenza.


To przynajmniej rozwiązuje ogólny problem. Wydaje mi się, że można by również stworzyć wersje listy sortowania wrażliwe na języki.
Lennart Regebro

Nie pozwala to na określenie ustawień regionalnych, a plik konfiguracyjny odniesienia powoduje błąd ValueError.
thebjorn

8

Możesz być także zainteresowany Pyuca :

http://jtauber.com/blog/2006/01/27/python_unicode_collation_algorithm/

Chociaż z pewnością nie jest to najdokładniejszy sposób, jest to bardzo prosty sposób, aby przynajmniej zrobić to trochę dobrze. Przebiega również ustawienia regionalne w aplikacjach internetowych, ponieważ ustawienia regionalne nie są bezpieczne dla wątków i ustawiają ustawienia języka w całym procesie. Jest również łatwiejszy w konfiguracji niż PyICU, który opiera się na zewnętrznej bibliotece C.

Przesłałem skrypt na github, ponieważ oryginał nie działał w momencie pisania tego tekstu i musiałem skorzystać z pamięci podręcznej sieci, aby go zdobyć:

https://github.com/href/Python-Unicode-Collation-Algorithm

Z powodzeniem użyłem tego skryptu do zdrowego sortowania tekstu niemieckiego / francuskiego / włoskiego w module plone.


+1 dla pyuca. Jest dość szybki (3 sekundy na posortowanie 28000 słów), jest czystym Pythonem i nie wymaga zależności.
michaelmeyer

7

Podsumowanie i rozszerzona odpowiedź:

locale.strcollw Pythonie 2 i locale.strxfrmfaktycznie rozwiąże problem i wykonuje dobrą robotę, zakładając, że masz zainstalowane odpowiednie ustawienie regionalne. Przetestowałem go również pod Windows, gdzie nazwy ustawień narodowych są myląco różne, ale z drugiej strony wydaje się, że domyślnie są zainstalowane wszystkie obsługiwane lokalizacje.

ICUniekoniecznie robi to lepiej w praktyce, jednak robi o wiele więcej . Przede wszystkim obsługuje rozdzielacze, które mogą dzielić teksty w różnych językach na słowa. Jest to bardzo przydatne w językach, w których nie ma separatorów słów. Będziesz musiał mieć zbiór słów, które posłużą jako podstawa do podziału, ponieważ nie są one uwzględnione.

Ma również długie nazwy ustawień regionalnych, dzięki czemu można uzyskać ładne nazwy wyświetlane dla ustawień regionalnych, obsługę kalendarzy innych niż gregoriański (chociaż nie jestem pewien, czy interfejs Pythona to obsługuje) i mnóstwo innych mniej lub bardziej niejasnych obsługiwanych ustawień regionalnych .

Podsumowując: jeśli chcesz sortować alfabetycznie i zależnie od lokalizacji, możesz użyć localemodułu, chyba że masz specjalne wymagania lub potrzebujesz więcej funkcji zależnych od lokalizacji, takich jak rozdzielacz słów.


6

Widzę, że odpowiedzi już wykonały świetną robotę, chciałem tylko wskazać jedną nieskuteczność kodowania w sortowaniu ludzkim . Aby zastosować selektywne tłumaczenie znak po znaku do ciągu znaków Unicode, używa kodu:

spec_dict = {'Å':'A', 'Ä':'A'}

def spec_order(s):
    return ''.join([spec_dict.get(ch, ch) for ch in s])

Python ma znacznie lepszy, szybszy i bardziej zwięzły sposób wykonania tego zadania pomocniczego (na łańcuchach Unicode - analogiczna metoda dla ciągów bajtów ma inną i nieco mniej pomocną specyfikację! -):

spec_dict = dict((ord(k), spec_dict[k]) for k in spec_dict)

def spec_order(s):
    return s.translate(spec_dict)

Dykt, który przekazujesz do translatemetody, ma liczby porządkowe Unicode (nie ciągi) jako klucze, dlatego potrzebujemy tego kroku przebudowy z oryginalnego znaku-znaku spec_dict. (Wartości w dyktandzie, które przekazujesz do przetłumaczenia [w przeciwieństwie do kluczy, które muszą być liczbami porządkowymi] mogą być liczbami porządkowymi Unicode, dowolnymi ciągami znaków Unicode lub Brak, aby usunąć odpowiedni znak jako część tłumaczenia, więc łatwo jest określić „ignoruj określony znak do celów sortowania ”,„ map ä to ae do celów sortowania ”i tym podobne).

W Pythonie 3 krok „przebudowy” jest prostszy, np .:

spec_dict = ''.maketrans(spec_dict)

Zobacz dokumentację, aby poznać inne sposoby użycia tej maketransmetody statycznej w Pythonie 3.


Ta metoda jest fajna, ale nie pozwala na umieszczenie á między az i b
Barney


1

Ostatnio do tego zadania używam zope.ucol ( https://pypi.python.org/pypi/zope.ucol ). Na przykład sortowanie niemieckiego ß:

>>> import zope.ucol
>>> collator = zope.ucol.Collator("de-de")
>>> mylist = [u"a", u'x', u'\u00DF']
>>> print mylist
[u'a', u'x', u'\xdf']
>>> print sorted(mylist, key=collator.key)
[u'a', u'\xdf', u'x']

zope.ucol obejmuje również OIOM, więc byłby alternatywą dla PyICU.


1

Kompletne rozwiązanie UCA

Najprostszym, najłatwiejszym i najprostszym sposobem wykonania tego jest wywołanie modułu biblioteki Perl, Unicode :: Collate :: Locale , który jest podklasą standardowego modułu Unicode :: Collate . Wszystko, co musisz zrobić, to przekazać konstruktorowi wartość locale "xv"dla Szwecji.

(Być może niekoniecznie doceniasz to w szwedzkim tekście, ale ponieważ Perl używa abstrakcyjnych znaków, możesz użyć dowolnego punktu kodu Unicode, który Ci się podoba - bez względu na platformę lub wersję! Niewiele języków oferuje taką wygodę. Wspominam o tym, ponieważ walczę z ostatnio przegrywała bitwę z Javą z powodu tego irytującego problemu.)

Problem polega na tym, że nie wiem, jak uzyskać dostęp do modułu Perla z Pythona - pomijając, to znaczy używając wywołania powłoki lub dwustronnego potoku. W tym celu dostarczyłem ci zatem kompletny skrypt roboczy zwany ucsort , który możesz wywołać, aby zrobić dokładnie to, o co prosiłeś, z doskonałą łatwością.

Ten skrypt jest w 100% zgodny z pełnym algorytmem sortowania Unicode , z obsługą wszystkich opcji dostosowywania !! A jeśli masz zainstalowany opcjonalny moduł lub korzystasz z Perla 5.13 lub nowszego, masz pełny dostęp do łatwych w użyciu ustawień regionalnych CLDR. Zobacz poniżej.

Demonstracja

Wyobraź sobie zestaw wejściowy uporządkowany w ten sposób:

b o i j n l m å y e v s k h d f g t ö r x p z a ä c u q

Domyślne sortowanie według punktu kodowego daje:

a b c d e f g h i j k l m n o p q r s t u v x y z ä å ö

co jest błędne w książce wszystkich. Korzystając z mojego skryptu, który używa algorytmu sortowania Unicode, otrzymujesz następującą kolejność:

% perl ucsort /tmp/swedish_alphabet | fmt
a å ä b c d e f g h i j k l m n o ö p q r s t u v x y z

To jest domyślne sortowanie UCA. Aby uzyskać szwedzkie ustawienie regionalne, zadzwoń do ucsort w ten sposób:

% perl ucsort --locale=sv /tmp/swedish_alphabet | fmt
a b c d e f g h i j k l m n o p q r s t u v x y z å ä ö

Oto lepsze demo wejścia. Najpierw zestaw wejściowy:

% fmt /tmp/swedish_set
cTD cDD Cöd Cbd cAD cCD cYD Cud cZD Cod cBD Cnd cQD cFD Ced Cfd cOD
cLD cXD Cid Cpd cID Cgd cVD cMD cÅD cGD Cqd Cäd cJD Cdd Ckd cÖD cÄD
Ctd Czd Cxd cHD cND cKD Cvd Chd Cyd cUD Cld Cmd cED Crd Cad Cåd Ccd
cRD cSD Csd Cjd cPD

Według punktu kodowego, to sortuje w ten sposób:

Cad Cbd Ccd Cdd Ced Cfd Cgd Chd Cid Cjd Ckd Cld Cmd Cnd Cod Cpd Cqd
Crd Csd Ctd Cud Cvd Cxd Cyd Czd Cäd Cåd Cöd cAD cBD cCD cDD cED cFD
cGD cHD cID cJD cKD cLD cMD cND cOD cPD cQD cRD cSD cTD cUD cVD cXD
cYD cZD cÄD cÅD cÖD

Ale użycie domyślnego UCA powoduje sortowanie w ten sposób:

% ucsort /tmp/swedish_set | fmt
cAD Cad cÅD Cåd cÄD Cäd cBD Cbd cCD Ccd cDD Cdd cED Ced cFD Cfd cGD
Cgd cHD Chd cID Cid cJD Cjd cKD Ckd cLD Cld cMD Cmd cND Cnd cOD Cod
cÖD Cöd cPD Cpd cQD Cqd cRD Crd cSD Csd cTD Ctd cUD Cud cVD Cvd cXD
Cxd cYD Cyd cZD Czd

Ale w szwedzkim lokalu tak:

% ucsort --locale=sv /tmp/swedish_set | fmt
cAD Cad cBD Cbd cCD Ccd cDD Cdd cED Ced cFD Cfd cGD Cgd cHD Chd cID
Cid cJD Cjd cKD Ckd cLD Cld cMD Cmd cND Cnd cOD Cod cPD Cpd cQD Cqd
cRD Crd cSD Csd cTD Ctd cUD Cud cVD Cvd cXD Cxd cYD Cyd cZD Czd cÅD
Cåd cÄD Cäd cÖD Cöd

Jeśli wolisz sortować wielkie litery przed małymi, zrób to:

% ucsort --upper-before-lower --locale=sv /tmp/swedish_set | fmt
Cad cAD Cbd cBD Ccd cCD Cdd cDD Ced cED Cfd cFD Cgd cGD Chd cHD Cid
cID Cjd cJD Ckd cKD Cld cLD Cmd cMD Cnd cND Cod cOD Cpd cPD Cqd cQD
Crd cRD Csd cSD Ctd cTD Cud cUD Cvd cVD Cxd cXD Cyd cYD Czd cZD Cåd
cÅD Cäd cÄD Cöd cÖD

Niestandardowe rodzaje

Możesz zrobić wiele innych rzeczy za pomocą ucsort . Na przykład, oto jak sortować tytuły w języku angielskim:

% ucsort --preprocess='s/^(an?|the)\s+//i' /tmp/titles
Anathem
The Book of Skulls
A Civil Campaign
The Claw of the Conciliator
The Demolished Man
Dune
An Early Dawn
The Faded Sun: Kesrith
The Fall of Hyperion
A Feast for Crows
Flowers for Algernon
The Forbidden Tower
Foundation and Empire
Foundations Edge
The Goblin Reservation
The High Crusade
Jack of Shadows
The Man in the High Castle
The Ringworld Engineers
The Robots of Dawn
A Storm of Swords
Stranger in a Strange Land
There Will Be Time
The White Dragon

Do uruchomienia skryptu będziesz potrzebować Perla 5.10.1 lub nowszego. Aby zapewnić obsługę ustawień regionalnych, należy albo zainstalować opcjonalny moduł CPAN Unicode::Collate::Locale. Alternatywnie możesz zainstalować wersje rozwojowe Perla, 5.13+, które standardowo zawierają ten moduł.

Konwencje telefoniczne

Jest to szybki prototyp, więc ucsort jest przeważnie nieudokumentowany. Ale to jest jego SKŁADNIA tego, jakie przełączniki / opcje akceptuje w wierszu poleceń:

    # standard options
    --help|?
    --man|m
    --debug|d

    # collator constructor options
    --backwards-levels=i
    --collation-level|level|l=i
    --katakana-before-hiragana
    --normalization|n=s
    --override-CJK=s
    --override-Hangul=s
    --preprocess|P=s
    --upper-before-lower|u
    --variable=s

    # program specific options
    --case-insensitive|insensitive|i
    --input-encoding|e=s
    --locale|L=s
    --paragraph|p
    --reverse-fields|last
    --reverse-output|r
    --right-to-left|reverse-input

Tak, ok: to naprawdę lista argumentów, której używam w wywołaniu Getopt::Long, ale masz pomysł. :)

Jeśli potrafisz dowiedzieć się, jak wywołać moduły biblioteki Perla bezpośrednio z Pythona bez wywoływania skryptu Perla, zrób to. Po prostu nie wiem, jak ja. Chciałbym się dowiedzieć, jak to zrobić.

W międzyczasie uważam, że ten skrypt zrobi to, czego potrzebujesz w każdym szczególe - a nawet więcej! Teraz używam tego do sortowania całego tekstu. W końcu robi to, czego potrzebowałem przez długi, długi czas.

Jedynym minusem jest to, że --localeargument powoduje spadek wydajności, chociaż jest wystarczająco szybki do regularnego, nielokalnego, ale nadal w 100% zgodnego z UCA sortowania. Ponieważ ładuje wszystko w pamięci, prawdopodobnie nie chcesz używać tego w dokumentach gigabajtowych. Używam go wiele razy dziennie i na pewno świetnie jest mieć wreszcie rozsądne sortowanie tekstu.


2
Po co do licha wywołać skrypt Perla, aby zrobić coś, do czego służą biblioteki Pythona?
Lennart Regebro

2
Bo nie wiem, nie było biblioteki Python, dlatego!
tchrist

@Lennart: Naprawdę wolę biblioteki natywne lub co najwyżej te połączone z interfejsem API C i ładowane dynamicznie (co czasami potrzebujesz). Nie uważam różnych rozwiązań PyPerl i Inline :: Perl za zbyt przekonujące, solidne lub elastyczne. Lub coś. Po prostu z pewnych powodów nie czują się dobrze. Ostatnio próbowałem tego, kiedy potrzebowałem dobrego wykrywania zestawu znaków (czego niestety nigdy nie miałem).
tchrist

4
Używanie Perla wewnątrz Pythona to po prostu uzależnienie.
Utku Zihnioglu

1
Łał. Tak - dla mnie wygląda jak Perl, w rzeczywistości widzimy, że są teraz więcej niż dwa sposoby robienia rzeczy :) Ale wywoływanie C z Pythona generalnie nie implikuje tego rodzaju dodatkowych zależności i praktycznych problemów z obsługą, które spowodowałoby wywołanie Perla, więc jego strasznie trudno dostrzec, że trzeba to zrobić w ten sposób.
nealmcb

0

To jest daleko od kompletnego rozwiązania dla przypadku użycia, ale można spojrzeć na unaccent.py skrypt z effbot.org. W zasadzie usuwa wszystkie akcenty z tekstu. Możesz użyć tego „oczyszczonego” tekstu do sortowania alfabetycznego. (Dokładniejszy opis znajduje się na tej stronie).


Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.