Программирование на языке Ruby
вернуться

Фултон Хэл
Шрифт:

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

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

U+0300
to
U+036F
:

def transform(str)

 Unicode.normalize_KD(str).unpack('U*').select{ |cp|

cp < 0x0300 || cp > 0x036F

 }.pack('U*')

end

array.map{|x| transform(x) } # ["epicurian", "epee", "elan"]

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

def collate(array)

 transformations = array.inject({}) do |hash, item|

hash[item] = yield item

hash

 end

 array.sort_by {|x| transformations[x] }

end

collate(array) {|a| transform(a) } # ["'elan", "'ep'ee", "epicurian"]

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

На самом деле в немецком языке есть несколько способов упорядочения; мы остановимся на стандарте DIN-2 (как в телефонном справочнике). Согласно этому стандарту, символ ss (эсцет) эквивалентен ss, а умляут эквивалентен букве е (то есть "o — то же самое, что ое и т.д.).

Наш метод трансформации должен учитывать эти детали. Снова начнем с декомпозиции составных символов. Например, модифицирующая трема (умляут) представляется кодовой позицией

U+0308
. За основу мы возьмем метод преобразования регистра, имеющийся в Ruby, но несколько дополним его. Вот как выглядит теперь код трансформации:

def transform_de(str)

 decomposed = Unicode.normalize_KD(str).downcase

 decomposed.gsub!('ss', 'ss')

 decomposed.gsub([0x0308].pack('U'), 'e')

end

array = ["Strasse", ""offnen"]

array.map {|x| transform_de(x) } # ["strasse", "oeffnen"]

He для всех языков годится такой прямолинейный подход. Например, в испанском между буквами n и о есть еще буква ~n. Однако, если каким-то образом сдвинуть оставшиеся буквы, то мы справимся и с этой проблемой. В листинге 4.1 для упрощения обработки нормализация применена к монолитным символам. Кроме того, мы облегчили себе жизнь, игнорируя различия между буквами с диакритическими знаками и без них.

Листинг 4.1. Упорядочение строк в испанском языке

def map_table(list)

 table = {}

 list.each_with_index do |item, i|

item.split(',').each do |subitem|

table[Unicode, normalize_KC(subitem)] = (?a + i).chr

end

 end

 table

end

ES_SORT = map_table(%w(

 a,A,'a,'A b,B c,C d,D е,Е,'e,'E f,F g,G h,H i,I,'i,'I j,J k,K l,L m,M

 n,N ~n,~N o,O,'o,'O p,P q,Q r,R s,S t,T u,U,u,U v,V w,W x,X y,Y z,Z

))

def transform_es(str)

 array = Unicode.normalize_KC(str).scan(/./u)

 array.map {|c| ES_SORT[c] || c}.join

end

array = %w['este estoy a~no apogeo amor]

array.map {|a| transform_es(a) }

# ["etue", "etupz", "aop", "aqpgep", "amps"]

collate(array) {|a| transform_es(a) }

# ["amor", "a~no", "apogeo", "'este", "estoy"]

В реальности упорядочение немного сложнее, чем показано в примерах выше; обычно требуется до трех уровней обработки. На первом уровне сравниваются только базовые символы без учета диакритических знаков и регистра, на втором учитываются диакритические знаки, а на третьем — регистр. Второй и третий уровень необходимы лишь в том случае, когда на предыдущих уровнях строки совпали. Кроме того, в некоторых языках последовательности, состоящие из нескольких символов, сортируются как единая семантическая единица (например, в хорватском lj расположено между l и m). Поэтому разработка языковозависимого или обобщенного алгоритма сортировки — задача нетривиальная: необходимо хорошо разбираться в конкретном языке. Невозможно изобрести по-настоящему универсальный алгоритм сортировки, который давал бы правильные результаты для всех языков, хотя попытки в этом направлении производились.