使用 Unicode 归类算法在 Ruby 中排序

Question

Ruby 和 Postgres 的排序略有不同，这在我的项目中引起了细微的问题。有两个问题：重音字符和空格。看起来 Ruby 正在按 ASCII 方式排序，而 Postgres 正在使用正确的 Unicode collation algorithm.

进行排序

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)

Ruby Heroku 上的 2.4.4。

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"

我可以修复重音字符的处理，但我无法 Ruby 正确处理空格。例如，这是他们对同一个列表进行排序的方式。

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

我试过 icunicode gem:

array.sort_by {|s| s.unicode_sort_key}

这会处理重音字符，但不会正确处理空格。

如何让 Ruby 使用 Unicode 归类算法进行排序？

UPDATE 在 Unicode® Technical Standard #10 中可以找到更全面的示例。这些顺序正确。

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

Answer 1

我将此算法与 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]
}

首先，我们使用删除了白色space 的unicode 排序键进行排序。然后如果它们相同，我们按原始值的 unicode 排序键排序。

这解决了 unicode_sort_key 的弱点：它不认为 space 是弱点。

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 中的 space 与任何其他字符一样重要。这导致 'fo p' < 'foo' 不正确。我们通过在生成密钥之前首先剥离 spaces 来解决这个问题。

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' 这是正确的。

但是由于规范化，我们的值可能在去除白色space 后看起来相同，fo o 应该小于foo。因此，如果 database_sort_keys 相同，我们比较它们的普通 unicode_sort_keys.

有一些边缘情况是错误的。 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

Answer 2

如果有任何机会将 Ruby 更新到 2.5.0，它会附带 String#unicode_normalize。后者将使任务变得更容易：您只需要 将字符串规范化为分解形式 ，然后再删除 non-letters。在输入中我们有 4 个字符串。在qüia中有组合变音符号，在'qü ic'中有组合字符：

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

然后，瞧：

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

Answer 3

您的用例是否允许简单地将排序委托给 Postgres，而不是尝试在 Ruby 中重新创建它？

这里的部分困难在于没有单一正确的排序方法，但任何可变元素都可能导致最终排序顺序出现相当大的差异，例如参见 the section on variable weighting。

例如，像 twitter-cldr-rb 这样的 gem 具有相当健壮的 UCA 实现，并得到综合测试套件的支持 - 但针对 non-ignorable 测试用例，它与 Postgres 实现不同（Postgres 似乎使用 shift-trimmed 变体）。

test cases 的绝对数量意味着您不能保证一个有效的解决方案在所有情况下都匹配 Postgres 排序顺序。例如。它会正确处理 en/em 破折号，甚至是表情符号吗？您可以分叉并修改 twitter-cldr-rb gem，但我怀疑这不是一件小事！

如果您需要处理数据库中不存在的值，您可以要求 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

它显然会导致 round-trip 到 Postgres，但应该非常快。

使用 Unicode 归类算法在 Ruby 中排序

Sorting in Ruby using the Unicode collation algorithm

ruby

postgresql

unicode

collation