Книга: Программирование на языке Ruby

4.2.5. Упорядочение строк

4.2.5. Упорядочение строк

Обычно, хотя и не всегда, строки упорядочиваются по алфавиту или сходным образом. Упорядочение тесно связано с нормализацией: в обоих случаях применяются одни и те же идеи и библиотеки.

Предположим, например, что мы хотим отсортировать такой массив строк:

eacute = [0x00Е9].pack('U')
acute = [0x0301].pack('U')
array = ["epicurian", "#{eacute}p#{eacute}e", "e#{acute}lan"]
# ["epicurian", "?р?е", "?lan"]

Что произойдет, если передать этот массив методу Array#sort?

array.sort # ["epicurian", "?lan", "?р?е"]

He годится!.. Попытаемся понять, почему так получилось. Сортируемые строки Ruby сравнивает побайтно. Чтобы убедиться в этом, достаточно взглянуть на первые несколько байтов каждой строки:

array.map {|item| "#{item}: #{item.unpack('С*')[0,3].join(',')}" }
# ["epicurian: 101,112,105", "?р?е: 195,169,112",
# "?lan: 101,204,129"]

Тут возникают две трудности. Во-первых, символы UTF-8, не имеющие аналога в кодировке ASCII, начинаются с байта, имеющего большое числовое значение, а стало быть, после сортировки неизбежно окажутся после ASCII-символов. Во-вторых, составные латинские символы оказываются раньше монолитных из-за первого ASCII-байта.

В системные библиотеки обычно включают функции сортировки, которые сравнивают строки в соответствии с правилами конкретного языка. В библиотеке, поставляемой вместе с компилятором языка С, для этого служат функции strxfrm и strcoll.

Имейте в виду, что проблема возникает даже в случае кодировки ASCII. При сортировке ASCII-строк в 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) } # ["?lan", "?p?e", "epicurian"]

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

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

Наш метод трансформации должен учитывать эти детали. Снова начнем с декомпозиции составных символов. Например, модифицирующая трема (умляут) представляется кодовой позицией U+0308. За основу мы возьмем метод преобразования регистра, имеющийся в Ruby, но несколько дополним его. Вот как выглядит теперь код трансформации:

def transform_de(str)
 decomposed = Unicode.normalize_KD(str).downcase
 decomposed.gsub!('?', 'ss')
 decomposed.gsub([0x0308].pack('U'), 'e')
end
array = ["Stra?e", "?ffnen"]
array.map {|x| transform_de(x) } # ["strasse", "oeffnen"]

He для всех языков годится такой прямолинейный подход. Например, в испанском между буквами n и о есть еще буква ?. Однако, если каким-то образом сдвинуть оставшиеся буквы, то мы справимся и с этой проблемой. В листинге 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,?,? b,B c,C d,D е,Е,?,? f,F g,G h,H i,I,?,? j,J k,K l,L m,M
 n,N ?,? 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[?ste estoy a?o apogeo amor]
array.map {|a| transform_es(a) }
# ["etue", "etupz", "aop", "aqpgep", "amps"]
collate(array) {|a| transform_es(a) }
# ["amor", "a?o", "apogeo", "?ste", "estoy"]

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

Оглавление книги