Сортировка в Ruby с использованием алгоритма сортировки Unicode - PullRequest
Новая
       53

Сортировка в Ruby с использованием алгоритма сортировки Unicode

8 голосов
/ 07 июня 2019

Ruby и Postgres сортируют немного по-разному, и это вызывает небольшие проблемы в моем проекте. Есть две проблемы: акцентированные символы и пробелы. Похоже, что Ruby сортирует ASCII-бетики, а Postgres сортирует с правильным алгоритмом сортировки Unicode .

Heroku Postgres 11.2. Сортировка базы данных en_US.UTF-8. 

psql (11.3, server 11.2 (Ubuntu 11.2-1.pgdg16.04+1))
...
=> select 'quia et' > 'qui qui';
 ?column? 
----------
 f
(1 row)
=> select 'quib' > 'qüia';
 ?column? 
----------
 t
(1 row)

Рубин 2.4.4 на Heroku. 

Loading production environment (Rails 5.2.2.1)
[1] pry(main)> 'quia et' > 'qui qui'
=> true
[2] pry(main)> 'quib' > 'qüia'
=> false
[3] pry(main)> ENV['LANG']
=> "en_US.UTF-8"

Я могу исправить обработку акцентированных символов, но не могу заставить Руби правильно делать пробелы. Например, вот как они сортируют один и тот же список. 

Postgres: ["hic et illum", "quia et ipsa", "qui qui non"]
Ruby:     ["hic et illum", "qui qui non", "quia et ipsa"]

Я пробовал icunicode самоцвет : 

array.sort_by {|s| s.unicode_sort_key}

Обрабатывает акцентированные символы, но неправильно пробелы.

Как мне заставить Ruby сортировать, используя алгоритм сортировки Unicode?

ОБНОВЛЕНИЕ Более подробный пример можно найти в Техническом стандарте Unicode® # 10 . Они в правильном порядке. 

  [
    "di Silva   Fred",
    "diSilva    Fred",
    "disílva    Fred",
    "di Silva   John",
    "diSilva    John",
    "disílva    John"
  ]

Ответы [ 3 ]

5 голосов
/ 08 июня 2019

Я очень близко подошел к этому алгоритму с icunicode gem . 

require 'icunicode'

def database_sort_key(key)
  key.gsub(/\s+/,'').unicode_sort_key
end

array.sort_by { |v|
  [database_sort_key(v), v.unicode_sort_key]
}

Сначала мы сортируем, используя ключ сортировки в Юникоде с удаленными пробелами.Затем, если они совпадают, мы сортируем по ключу сортировки в юникоде исходного значения.

Это работает вокруг слабости в unicode_sort_key: пробелы не считаются слабыми. 

2.4.4 :007 > "fo p".unicode_sort_key.bytes.map { |b| b.to_s(16) }
 => ["33", "45", "4", "47", "1", "8", "1", "8"] 
2.4.4 :008 > "foo".unicode_sort_key.bytes.map { |b| b.to_s(16) }
 => ["33", "45", "45", "1", "7", "1", "7"]

Обратите внимание, что пробел в fo p так же важен, как и любой другой символ.Это приводит к 'fo p' < 'foo', что неверно.Мы работаем над этим, сначала удаляя пробелы перед генерацией ключа. 

2.4.4 :011 > "fo p".gsub(/\s+/, '').unicode_sort_key.bytes.map { |b| b.to_s(16) }
 => ["33", "45", "47", "1", "7", "1", "7"] 
2.4.4 :012 > "foo".gsub(/\s+/, '').unicode_sort_key.bytes.map { |b| b.to_s(16) }
 => ["33", "45", "45", "1", "7", "1", "7"]

Теперь 'foo' < 'fo p', что правильно.

Но из-за нормализации у нас могут быть значения, которые выглядят както же самое после удаления пробела, fo o должно быть меньше foo.Поэтому, если database_sort_key s одинаковы, мы сравниваем их простые unicode_sort_key s.

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

Вот как Enumerable методов. 

module Enumerable
  # Just like `sort`, but tries to sort the same as the database does
  # using the proper Unicode collation algorithm. It's close.
  #
  # Differences in spacing, cases, and accents are less important than
  # character differences.
  #
  # "foo" < "fo p" o vs p is more important than the space difference
  # "Foo" < "fop" o vs p is more important than is case difference
  # "föo" < "fop" o vs p is more important than the accent difference
  #
  # It does not take a block.
  def sort_like_database(&block)
    if block_given?
      raise ArgumentError, "Does not accept a block"
    else
      # Sort by the database sort key. Two different strings can have the
      # same keys, if so sort just by its unicode sort key.
      sort_by { |v| [database_sort_key(v), v.unicode_sort_key] }
    end
  end

  # Just like `sort_by`, but it sorts like `sort_like_database`.
  def sort_by_like_database(&block)
    sort_by { |v|
      field = block.call(v)
      [database_sort_key(field), field.unicode_sort_key]
    }
  end

  # Sort by the unicode sort key after stripping out all spaces. This provides
  # a decent simulation of the Unicode collation algorithm and how it handles
  # spaces.
  private def database_sort_key(key)
    key.gsub(/\s+/,'').unicode_sort_key
  end
end
3 голосов
/ 17 июня 2019

Позволяет ли ваш вариант использования просто делегировать сортировку Postgres, а не пытаться воссоздать ее в Ruby?

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

Например, гем типа twitter-cldr-rb имеет довольно надежную реализацию UCA и поддерживается всеобъемлющим набором тестов, но в отличие от невосполнимых тестовых примеров, которые отличаются из реализации Postgres (похоже, Postgres использует вариант, урезанный смещением).

Само число тестовых случаев означает, что вы не можете гарантировать, что одно рабочее решение будет соответствовать порядку сортировки Postgres во всех случаях . Например. будет ли он правильно обрабатывать ан / эм тире или даже смайлики? Вы можете раскошелиться и модифицировать драгоценный камень twitter-cldr-rb, но я подозреваю, что это не будет маленьким начинанием!

Если вам нужно обработать значения, которых нет в базе данных, вы можете попросить Postgres облегчить их сортировку, используя список VALUES: 

sql = "SELECT * FROM (VALUES ('de luge'),('de Luge'),('de-luge'),('de-Luge'),('de-luge'),('de-Luge'),('death'),('deluge'),('deLuge'),('demark')) AS t(term) ORDER BY term ASC"
ActiveRecord::Base.connection.execute(sql).values.flatten

Это, очевидно, приведет к поездке в оба конца в Postgres, но, тем не менее, должно быть очень быстрым.

0 голосов
/ 08 июня 2019

Если есть шанс обновить Ruby до 2.5.0, он поставляется с String#unicode_normalize. Последнее упростит задачу: все, что вам нужно, это нормализовать строку в разложенную форму , прежде чем избавляться от не-букв. На входе у нас есть 4 строки. В qüia есть объединенные диакритические знаки , в 'qü ic' есть составной символ: 

['quid', 'qüia', 'qu ib', 'qü ic'].map &:length
#⇒ [4, 5, 5, 5]

и, вуаля: 

['quid', 'qüia', 'qu ib', 'qü ic'].sort_by do |s|
  s.unicode_normalize(:nfd).gsub(/\P{L}+/, '')
end
#⇒ ["qüia", "qu ib", "qü ic", "quid"]

Для сортировки без учета регистра, String#downcase внутри сортировщика: 

["di Silva Fred", "diSilva Fred", "disílva Fred",
 "di Silva John", "diSilva John", "disílva John"].sort_by do |s|
  s.downcase.unicode_normalize(:nfd).gsub(/\P{L}+/, '')
end
#⇒ ["di Silva Fred", "diSilva Fred", "disílva Fred",
#   "di Silva John", "diSilva John", "disílva John"]
...