Slicing and Dicing Unicode Properties

http://www.sw.it.aoyama.ac.jp/2018/pub/IUC42_properties/

Internationalization and Unicode Conference 42
Santa Clara, CA, U.S.A., September 11, 2018

Martin J. DÜRST

duerst@it.aoyama.ac.jp, Aoyama Gakuin University

© 2017-8 Martin J. Dürst, Aoyama Gakuin University

Introduction

Motivation:
Slide from Ruby Kaigi 2016

• Unicode provides a wide range of character properties
• Most available in Regexp
  
• Does this string contain a Hiragana character?
  'Юに코δ' =~ /\p{Hiragana}/
• What script is 'Ю'?
  sorry, impossible!
• Currently looking at this with a student, hopefully
  • For Ruby ~2.5
  • Use less memory
  • Faster
  • More properties
  • More ways to use

Outline

• Introduction
  • Audience Self-Intro
  • Speaker Self-Intro
  • Ruby and Regular Expressions
• Unicode Properties
• Improving Property Implementation in Ruby Regular Expressions
• Conclusions

Audience Self-Intro

• Who has heard about Unicode properties?

Audience Self-Intro

• Who has heard about Unicode properties?
• Who knows an Unicode property?

Audience Self-Intro

• Who has heard about Unicode properties?
• Who knows an Unicode property?
• Who has used regular expressions?

Audience Self-Intro

• Who has heard about Unicode properties?
• Who knows an Unicode property?
• Who has used regular expressions?
• Who has used Unicode properties with regular expressions?

Audience Self-Intro

• Who has heard about Unicode properties?
• Who knows an Unicode property?
• Who has used regular expressions?
• Who has used Unicode properties with regular expressions?
• Who has used Unicode properties in an implementation?

Speaker Self-Intro

• From Switzerland, living and working in Japan
• Research and teaching at Aoyama Gakuin University
• Teaching: Algorithms, Compilers, C programming, Math for CS students, Functional Programming,..., in Japanese and English
• Research topics: Software Internationalization,
  World Wide Web Architecture, Programming Languagues
• W3C Internationalization Interest Group Chair, IETF WG member,...
• Ruby Committer

Ruby

• Created by Yukihiro Matsumoto (Matz; since 1993)
• Easy for beginners,
  deep for experts
• Object-oriented throughout, but not obtrusive
• Extremely flexible
• Particularly strong for (internal) DSLs, metaprogramming, Web programming (Ruby on Rails)

Basic Ruby

5.times { puts "Hello Ruby!" }

• Everything is an object
• Unobtrusive syntax (no need for semicolons, ...)
• Methods can take blocks ({ ... } or do ... end)
  (blocks in other programming languages: lambda/closure/anonymous function)

Conventions Used

Code is mostly green, monospace
puts 'Hello Ruby!'

Variable parts are orange
puts "some string"

Results are indicated with "⇒"
1 + 1 ⇒ 2

Matching of regular expressions is indicated with ≟, ≅, or ≇
'abc' ≅ /a/; 'def' ≇ /a/

Matching substrings are indicated with orage background

'abcba' ≅ /b/

This slide shows you the conventions we'll use throughout the talk. (Code is in green monospace font. Variable parts are in orange. Where necessary, the character encoding of a string is indicated with a blue subsccript. Results are show after a double arrow. We'll use two symbols to show when regular expressions match or don't match.)

Our Contributions to Ruby

Mainly in the following areas:

• Encoding conversion (String#encode, Ruby 1.9)
• Unicode normalization (String#unicode-normalize, Ruby 2.2)
• Non-ASCII case conversion (String#upcase,..., Ruby 2.4)
• Unicode version updates

As a Ruby committer, I'm mostly responsible for the areas listed on this slide.

Ruby Versions and Unicode Versions

NOTE about Ruby versions and Unicode versions: The Ruby core team is very conservative (in my view too conservative) in introducing new Unicode versions as bug fixes. Update to new Unicode versions therefore only happens for new Ruby versions.

RbConfig::CONFIG["UNICODE_VERSION"] ⇒ '10.0.0'

V_Unicode = y - 2007; V_Ruby = (y - 1992) · 0.1

V_Ruby = 1.5 + V_Unicode · 0.1      V_Unicode = V_Ruby · 10 - 15

Don't extrapolate too far!

Georgian Mtavruli

• Uppercase variants of lowercase Mkhedruli
• Added in Unicode 11.0.0
• Not used in titlecase
• No good font support yet
• Advice on how to handle greatly appreciated!
• See issue #14839

Outline

• Introduction
• Unicode Properties
  • What is Unicode
  • Properties as a big table
  • How to save space
• Improving Property Implementation in Ruby Regular Expressions
• Conclusions

Unicode is ...

• A coded character set for writing the languages of the world

Unicode is ...

• A coded character set for writing the languages of the world
  But so is ISO/IEC 10646 (and GB 18030 and JIS X 0221 and ...)

Unicode is ...

• A coded character set for writing the languages of the world
  But so is ISO/IEC 10646 (and GB 18030 and JIS X 0221 and ...)
• With lots of information about each character
• With ways of how to use this information in applications

Unicode is ...

• A coded character set for writing the languages of the world
  But so is ISO/IEC 10646 (and GB 18030 and JIS X 0221 and ...)
• With lots of information about each character
  ⇒ With many properties about each character
• With ways of how to use this information in applications
  ⇒ Used by algorithms

Examples of Properties and Algorithms

• Character classification
• Bidi (bidirectional rendering) properties and algorithm
• Normalization algorithms and related properties
• Word and line breaking algorithms and properties

For a list of properties, see Unicode Character Database, UAX #44, in particular Table 9

For some background on Unicode properties, see The Unicode Property Model, UTR #23 (caution: very dry reading)

Properties and Regular Expressions

• Properties can be used in regular expressions
• Regular expressions describe patterns that are matched against strings
  E.g.: Find all the bs in the string 'abcba':

  'abcba' ≅ /b/

• Patterns allow to describe repetition, alternatives, contexts,...
• Properties match classes of characters

See also Unicode Regular Expressions, UTS #18

Properties in Regular Expressions

• Check for a character with a property with \p{property}
  Examples:
  \p{Digit} (match a digit)
  \p{Hiragana} (match a Hiragana)
  
• Negative check with \P{property} or \p{^property}

  Examples:
  \p{^Digit} or \P{Digit} (match everything else than a digit)
  \p{^Hiragana} or \P{Hiragana} (match everything else than a Hiragana)
  

• Check for property values with \p{property=value}
  Example:
  'a€青ሙឈ' ≅ /\p{Age=2.0}/ (all characters defined in Unicode 2.0)

How to Think about Properties

• There are characters (and unassigned codepoints)
  'a', '青', "\u03A2"
• There are properties
  General Category, Script, Age, Combining Class,...
• Each codepoint has a property value for each character
  'あ'.property('script') ⇒ Hiragana, or
  'あ'.script ⇒ Hiragana

How to Organize Property Data

• There are characters (and unassigned codepoints)

  ⇒ List them from top to bottom at the left

• There are properties

  ⇒ List them from left to right at the top

• Each codepoint has a property value for each character

  ⇒ Put each property value in the corresponding cell

⇒ All properties represented in a big table

How Big is this Table?

• Number of Unicode code points (17 planes): 17 * 2¹⁶ = 1'114'112
• Number of Unicode properties: ~100
  (109 when counting through Table 9 in UAX #44)
• Number of cells: ~111'411'200

How Big is this Table?

• Number of Unicode code points (17 planes): 17 * 2¹⁶ = 1'114'112
• Number of Unicode properties: ~100
  (109 when counting through Table 9 in UAX #44)
• Number of cells: ~111'411'200

• This is a really huge table
• As an example, Excel (2013) wouldn't handle it:

  Last row in Excel (2013): 1'048'576 = 2²⁰ < 1'114'112

• To compare: Google Docs: 40'000
• Direct storage very inefficient, need ideas to improve

Any Better Ideas?

Properties of properties that we may be able to exploit:

• Property values
• Sparsity
• Dependence
• Regularity
• Continuity
• Equivalence

Exploiting Property Values

• Observation: There are different types of properties
  (see The Unicode Character Property Model, UTR #23)
  • Binary Property: T(rue) or F(alse)
  • Enumerated/Catalog Property: Small set of values, possibly extended over time
  • Numeric Property
  • String-Valued Property
• Use only the minimum number of bits for each property
  • Binary Property: One bit per character (~140'000 bytes)
  • Enumerated Property: ⌈log₂ n⌉ bits for a property with n possible values
    (e.g. 4 bits for a property with 13 values,...)

Exploiting Sparsity

• Many properties have a default value
• For many properties, most characters have the default value
• That means that the property values are sparsely populated
• One way to exploit this is a hash table (aka dictionary)

Exploiting Sparsity: Example 1

• In Efficient Pure Ruby Unicode Normalization (EPRUN, now part of Ruby proper)
• Pure Ruby Hash for Canonical Combining Class
  • Default for Combining Class is 0
  • Only for 849 code points Combining Class is not 0
  • Code fragment:
    

    class_table = {
    "\u0300"=>230, "\u0301"=>230, "\u0302"=>230, "\u0303"=>230,
    "\u0304"=>230, "\u0305"=>230, "\u0306"=>230, "\u0307"=>230,
    "\u0308"=>230, "\u0309"=>230, "\u030A"=>230, "\u030B"=>230,
    

• Together with other properties and data, ~182'000 bytes of program text
• When loaded, apparently ~2.6MB of memory

Exploiting Sparsity: Example 2

• Hash implementation in scripting language is general purpose
• Dedicated hash function can be more efficient
• Property data is stable, so hash function can be optimized
• GNU gperf is a tool that finds perfect hash functions (no collisions)
• Used for case conversion in Ruby (implemented in C)
• For further background, see Ups and Downs of Ruby Internationalization

Exploiting Dependence

• Some properties and values depend on other properties and values
• Examples:
  • Properties explicitly declared as dependent
  • Uppercase Letter → Letter
  • Possibly for accidental/undiscovered dependencies

Exploiting Regularity

• Some properties, for some character ranges, are regular
• These property values can be calculated algorithmically
• Examples:
  • CJKV Ideograph/Hangul names
    E.g.: CJK UNIFIED IDEOGRAPH-3400
  • Hangul (de)composition

Exploiting Continuity

• Looking a table column by column
• In many columns in the big table, there are stretches with repeated values
• This is a result of Unicode encoding similar characters close together
• Examples:
  • Blocks (obviously)
  • Scripts
  • Age
• Related to sparsity
• Can be exploited for data compression

Exploiting Equivalence

• Looking a table row by row
• Many characters have exactly the same collection of property values
  (need to exclude character-unique properties such as name)
• We can form equivalence classes:
  • All characters with identical properties belong to the same equivalence class (same color)
  • If the number of equivalence classes is low, representation can be quite compact
• Property value lookup is indirect
  Character → equivalence class → property value

Any Better Ideas? 

How each exploit works:

• Property values ⇒ squeezing bits
• Sparsity ⇒ using hash tables
• Dependence
• Regularity ⇒ algorithmic conversion
• Continuity ⇒ inversion lists
• Equivalence ⇒ grouping characters with the same property values

Outline

• Introduction
• Unicode Properties
• Improving Property Implementation in Ruby Regular Expressions
  • Importance of properties in Ruby
  • Current implementation: Inversion Lists
  • New implementation: Equivalence Classes
  • Experimental results
• Conclusions

Improving Unicode Property Support in Ruby

Importance of Unicode Properties in Ruby

• Internationalization in Ruby:
  • Encodings
  • Normalization,...
  • Regular Expressions ⇒ Properties
    Somebody: I have an internationalization problem.
    Matz: Why don't you use regular expressions.

Ruby Regular Expression Engine

• Oniguruma (鬼車, devil's wheel)
• Onigumo (おにぐも)
  • Forked from Oniguruma
  • 鬼雲? (devil's cloud)
  • 鬼蜘蛛? (devil's spider)
    • Dangerous Japanese spider
    • Name used in various Manga

Properties in Regular Expressions

• Check for a character with a property with \p{}
  • Examples (positive):
    \p{Digit} (match a digit)
    \p{Hiragana} (match a Hiragana)
    
  • Examples (negative):
    \p{^Digit} or \P{Digit} (match everything else than a digit)
    \p{^Hiragana} or \P{Hiragana} (match everything else than a Hiragana)
    
• Usable inside character class
  • Example (logical OR):
    [\p{Digit}\p{Hiragana}] (match a digit or a Hiragana)
    
  • Example (logical AND):
    [\p{Tamil}&&\p{Digit}] (match Tamil digits: ௦௧௨௩௪௫௬௭௮௯)

In regular expressions, we can check for character properties with backslash-p. We can use this also inside character classes, where logical operations are also available.

Currently Supported Properties

• List of supported properties and values
• Very good support for binary properties (55/60)
• Not much support for multi-valued properties (7/43)
• Why this difference?

(as of Unicode 9.0.0)

Due to Onigmo, Ruby currently has very good support for Boolean properties. But the support for enumerated properties is not up to par. As we will see soon, the reason for this lies in the details of the Onigmo implemenation.

Current Implementation: Data for Boolean Property

From enc/unicode/10.0.0/name2ctype.h

/* 'Radical': Binary Property */
static const OnigCodePoint CR_Radical[] = {
        3,                /* number of intervals */
        0x2e80, 0x2e99,   /* ⺀ ~ ⺙ */
        0x2e9b, 0x2ef3,   /* ⺛ ~ ⺀ */
        0x2f00, 0x2fd5,   /* ⼀ ~ ⺀ */
}; /* CR_Radical */

• Exploiting continuity along a table column
• Values are boundaries of intervals
• Inside the intervals, the property is true
• Outside the intervals, the property is false

This is the data used for implementing the "Radical" property, which indicates whether a character is a Kanji radical or not. The values are the boundaries of intervals. Inside the boundaries, the property is true, outside, it is false.

Current Implementation: Inversion Lists

• Values are boundaries of intervals

          0x2e80, 0x2e99,   /* ⺀ ~ ⺙ */

• This means:
  "Radical" starts at U+2e80 and goes up to U+2e99, and so on
• In other words:
  Invert from non-Radical to Radical at U+2e80
  Invert from Radical to non-Radical at U+2e99
• This is called an Inversion List

The data values are the boundaries of the intervals. At the boundaries, the value of the property is inverted. This kind of data structure is therefore called "Inversion List".

Current Implementation: Enumerated Properties

• Inversion lists work well for binary properties
• Enumerated properties cannot be implemented directly
• Enumerated properties are decomposed:
  One inversion list for each property value
• Example: Script Property
  
  • Example values: Latin, Greek, Arabic, Tamil, Hiragana, Katakana,...
  • Total number of values: 138 in Unicode 10.0.0

Inversion lists work well for binary properties. But they cannot be used directly for enumerated properties. For enumerated properties, an inversion list has to be provided for each property value. As an example, the Script Property needs 138 inversion lists.

Additional Example: Data for Katakana

/* 'Katakana': Script */
static const OnigCodePoint CR_Katakana[] = {
        8,                /* number of intervals */
        0x30a1, 0x30fa,   /* ァ ~ ヺ */
        0x30fd, 0x30ff,   /* ヽ ~ ヿ */
        0x31f0, 0x31ff,   /* ㇰ ~ ㇿ */
        0x32d0, 0x32fe,   /* ㋐ ~ ㋾ */
        0x3300, 0x3357,   /* ㌀ ~ ㍗ */
        0xff66, 0xff6f,   /* ｦ ~ ｯ */
        0xff71, 0xff9d,   /* ｱ ~ ﾝ */
        0x1b000, 0x1b000, /* KATAKANA LETTER ARCHAIC E */
}; /* CR_Katakana */

Here's another example, the inversion list for the property value "Katakana" of the property "Script".

Current Implementation: Property Check

From regcomp.c, function onig_is_in_code_range:

  for (low = 0, high = n; low < high; ) {
    x = (low + high) >> 1;
    if (code > data[x * 2 + 1])
      low = x + 1;
    else
      high = x;
  }
  return ((low < n && code >= data[low * 2]) ? 1 : 0);

Binary search!

Execution time dependent on length of inversion list

As you can see from this code, properties are checked by using binary search on an inversion list. The execution time depends on the length of the inversion list.

Current Implementation: Data Size

• enc/unicode/10.0.0/name2ctype.h is 38'088 lines, 767'874 bytes
• 535 inversion lists (Unicode 9.0.0)
• 30'018 intervals (Unicode 9.0.0)
• Shortest inversion list: 1 interval
• Longest inversion list: 791 intervals
  

  /* 'Grapheme_Base': Derived Property */
  static const OnigCodePoint CR_Grapheme_Base[] = {
          791,
          0x0020, 0x007e,

• OnigCodePoint is 4 bytes
• Total memory usage:
  (535 + 30'018 · 2) · 4 = 252'284 bytes
• Compiled into enc/unicode.o (688'263 bytes on Cygwin)

This slide shows the calculations for the total memory needed by the current implementation. For Unicode Version 9, there are 535 inversion lists, about 30'000 intervals. This results in a total memory usage of about 250KB.

File Size

enc/unicode/10.0.0/name2ctype.h is 38'088 lines, 767'874 bytes

Trying to download from https://svn.ruby-lang.org/:

An Exception Has Occurred

Display of files larger than 512 KB disallowed by configuration

HTTP Response Status

403 Forbidden

Fortunately, checkout with svn (or github) works

One more way to show how large the file is.

New Approach: Equivalence Classes

• Core observations:
  • Look at rows (horizontal), not columns (vertical)
  • There are many characters where all properties are the same
    ⇒ exploit equivalence
• Group such characters into equivalence classes
• Unicode 9.0.0: 3747 equivalence classes

See Feature #13240

So can we improve on the current implementation? We'll try with the following approach. First, in our big spreadsheet, we look not at columns, but rows. We find that many rows are exactly identical. We group such rows/characters into equivalence classes. In Unicode Version 9, there are 3747 equivalence classes.

New Approach: Property Representation

• Each property is represented with a number of bits
• Exploiting property values
• Examples:
  Uppercase: Boolean property ⇒ 1 bit
  Script: 137 property values (scripts) ⇒ 8 bits
• Properties are grouped into words (32 bits)
• In Unicode 9.0.0, 192 bits (24 bytes, 6 words) needed
• Each property-value combination(e.g. Script=Katakana) is identified by
  1. Word number
  2. Bit mask for property
  3. Bit pattern for property value

We represent each property with a number of bits. Boolean propertios need only one bit. The Script property, which has 137 varues, needs 8 bits.

New Approach: Property Check

  /* get Property Value data */
  propVal = propValInfo[ctype];
  /* get bit pattern for equivalence class */
  return (propertyData[equivClass]
                      /* select word */
                      [propVal.word]
          /* extract property value bit pattern */
          & propVal.mask
           /* check for matching property value pattern */
         ) == propVal.value ? 1 : 0;

Constant-time lookup!

The processing needed to check for a property value is slightly complicated, but can be done in constant time.

Property Check Example

    /* data for equivalence class of Hiragana 「こ」 */
    10000111001000000011000010100010

    /* mask for Script property */
&   00000000111111110000000000000000

    /* bit pattern for property value Hiragana */
=   00000000001000000000000000000000

    /* result is same as bit pattern ⇒「こ」 is Hiragana */
==  00000000001000000000000000000000

This is an example with actual data. We are checking whether the Hiragana character "ko" is a Hiragana or not.

New Approach: Data Size (first try)

• Data for equivalence classes:
  3747 · 24 = 89'928 bytes
• Codepoint → equivalence class:
  17 · 2¹⁶ · 2 = 2'228'224 bytes
• Total:
  2'318'152 bytes
• Way too much!
• Improvements needed!

In this new implementation, we need to know the equivalence class of each code point. That still needs too much memory. We need another improvement.

New Approach: Two-Step Equivalence Class Lookup

• Group equivalence class information into slices of 256 characters
• Find slices that are exactly the same
  
• Examples:
  • All Kanji
  • All empty
• Structure as a two-layer DAG (direct acyclic graph)
• Character code → Slice → Equivalence class → Bit sequence → Masking → Property value

By using a two-step lookup for equivalance classes, we can save a lot of memory.

New Approach: Data Size (second try)

• Codepoint → slice:
  17 · 2¹⁶/256 · 1 = 4'352 bytes
• Slices:
  210 · 256 · 2 = 107'520 bytes
• Equivalence classes:
  3747 · 24 = 89'928 bytes
• Property Values:
  1009 · 3 · 4 = 12'108 bytes
• Total:
  213'908 bytes
• Looks good!

As a result, we happen to get by with 213KB of data.

Performance Experiments

• Machine
  • 3.33 GHz Intel Core i5
• Software
  • Windows 10 Enterprise 64 bit OS
  • x86_64 Cygwin
  • ruby 2.5.0dev (2016-12-27 trunk 57204)
• Data
  • 10 characters:
    a, Б, س, क, ∉, こ, 青, 가, ‚, 
  • Run property checks 10 million times
  • Innermost method call only

This is the setup for our performance experiments.

Processing Speedsparsity

As you can see, in the current implementation, processing gets slower if the number of intervals in the inversion list increases. Consistent with binary lookup, the increase is proportional to the logarithm of the number of intervals. In the new implementation, for every property value, we achieve about the same low time as for the property value with the lowest time in the current implemenation.

Property Discrimination

• Regular expression's \p checks for one specific value
  Example: Is this a Hiragana?
• Sometimes, we want to know e.g. the script of a character
• Does this string contain a Hiragana character?
  'Юに코δ' =~ /\p{Hiragana}/
• What script is 'Ю '?
  sorry, impossible with inversion lists! 不可能!
• Becomes possible with equivalence classes

See Feature#13241

With regular expressions, you can check characters for specific property values. However, it's not possible to ask what property value for a property that a character has. With an implementation based on eqivalence classes, providing this functionality becomes easy.

Old versus New

This is a comparison of the old and the new implementation.

Slide from Ruby Kaigi 2016

• Unicode provides a wide range of character properties
• Most available in Regexp
  
• Does this string contain a Hiragana character?
  'Юに코δ' =~ /\p{Hiragana}/
• What script is 'Ю'?
  sorry, impossible! 不可能!
• Currently looking at this with a student, hopefully
  • For Ruby ~2.5 ×
  • Use less memory ○
  • Faster ○
  • More properties ○
  • More ways to use ○

Comming back to the slide from Ruby Kaigi 2016, we see that most of our predictions were realized.

Future Work

• Not yet full implementation
• Need to coordiante with Onigmo
• Combinations of property checks may get slower
  • Inversion lists allow logical operations
    (E.g. inversion list ∧ inversion list → inversion list)
  • For equivalence classes, logical operation at run time
• May be solved by JIT compilation
• May be solved by creating "custom properties" for frequently used combinations
  (e.g. Kana: Hiragana ∨ Katakana)
• More ideas for "custom properties"
• Research ongoing

The new implementation also has some problems, but we are continuing research.

Acknowledgments

• Takumi Koyama (小山 拓美) for his help with Unicode Properties
• Ayumu Nojima (野島 歩) for his help with Unicode Normalization
• Many other students for help with research and implementations
• Openclipart for the World icon
• Yui Naruse (成瀬 ゆい), Nobu Nakada (中田 伸悦) and many other Ruby committers for help and support
• Matz (まつもと ゆきひろ) for Ruby, a programmer's best friend
• All the people involved in Unicode
• Amaya, Opera 12.17, and coderay for slide production and display
• Nozomi Kikuchi (菊池 のぞみ) and SVuGy (sorry, unpublished version) for creating the graphs

I want to deeply thank the many people who have contributed to this research and this preparation.

Summary

• Properties are a very important part of the Unicode Standard
• Properties can be visualized as a huge table
• There are many ways to compress this table
• Using the right compression can improve implementations
  (such as Ruby regular expressions)

Q & A

For more questions and comments, please contact me
(mailto:duerst@it.aoyama.ac.jp)

The latest version of this presentation is available at:

http://www.sw.it.aoyama.ac.jp/2018/pub/IUC42_properties/