CJK char frequency

TL;DR

• good news is that there are definitely commonly used chinese characters that we can bundle together into special glyph PBFs.
• bad news is that this amounts to about ~3000-4000 characters which will amount to a ~2-3MB overhead and it's not likely we can reduce this overhead much.
• other good news is this approach will likely work for hangul (korean) which has similar size/range waste issues though not as bad as cjk.

Notes from weekend analysis (source committed here https://github.com/mapbox/fontserver/tree/char-spec/spec).

Background

• There are a lot of chinese characters -- "Chinese characters are theoretically an open set" -- and a modern dictionary puts the number in the 100,000+.
• The problem we're dealing with is pretty well discussed especially in relation to learning chinese. Most discussions put the "99%" use character count at around 3000-4000 chars (e.g. http://www.commonchinesecharacters.com/Lists/MostCommon2500ChineseCharacters).

Prep

• Sample of text that we need to render. In spec/fixtures/ I've added 12 z14 vector tiles of major chinese cities.
• 4096 most frequent chinese characters, in all name tags from OSM. This is dumped to cjk-osm.json.
• 4096 most frequent chinese characters, from an academic analysis of modern chinese character frequency (http://lingua.mtsu.edu/chinese-computing/statistics/). This is dumped to cjk-modern.json.

Approach

Assuming a character that falls into the 4096 most freq character use can be grabbed from a set of CJK common PBFs or so, we can analyze the range count for our 12 vector tiles:

none (78 ranges)
[ '0-255',
  '19968-20223',
  '20224-20479',
  '20736-20991',
  '20992-21247',
  '21248-21503',
  '21504-21759',
  '21760-22015',
  '22016-22271',
  '22272-22527',
  '22528-22783',
  '22784-23039',
  '23040-23295',
  '23296-23551',
  '23552-23807',
  '23808-24063',
  '24064-24319',
  '24320-24575',
  '24576-24831',
  '24832-25087',
  '25088-25343',
  '25344-25599',
  '256-511',
  '25600-25855',
  '25856-26111',
  '26112-26367',
  '26368-26623',
  '26624-26879',
  '26880-27135',
  '27136-27391',
  '27392-27647',
  '27648-27903',
  '27904-28159',
  '28160-28415',
  '28416-28671',
  '28672-28927',
  '28928-29183',
  '29184-29439',
  '29440-29695',
  '29696-29951',
  '29952-30207',
  '30208-30463',
  '30464-30719',
  '30720-30975',
  '30976-31231',
  '31232-31487',
  '31488-31743',
  '31744-31999',
  '32000-32255',
  '32256-32511',
  '32512-32767',
  '32768-33023',
  '33280-33535',
  '33536-33791',
  '33792-34047',
  '34048-34303',
  '34304-34559',
  '34560-34815',
  '34816-35071',
  '35072-35327',
  '35584-35839',
  '35840-36095',
  '36096-36351',
  '36608-36863',
  '36864-37119',
  '37120-37375',
  '37888-38143',
  '38144-38399',
  '38400-38655',
  '38656-38911',
  '38912-39167',
  '39168-39423',
  '39424-39679',
  '39936-40191',
  '40448-40703',
  '40704-40959',
  '8192-8447',
  '8448-8703' ]

osm (26 ranges)
[ '0-255',
  '20224-20479',
  '20992-21247',
  '256-511',
  '28416-28671',
  '29440-29695',
  '29952-30207',
  '33536-33791',
  '38912-39167',
  '8192-8447',
  '8448-8703',
  'cjk-common-0',
  'cjk-common-1',
  'cjk-common-10',
  'cjk-common-11',
  'cjk-common-12',
  'cjk-common-13',
  'cjk-common-14',
  'cjk-common-2',
  'cjk-common-3',
  'cjk-common-4',
  'cjk-common-5',
  'cjk-common-6',
  'cjk-common-7',
  'cjk-common-8',
  'cjk-common-9' ]

modern (34 ranges)
[ '0-255',
  '22272-22527',
  '256-511',
  '26880-27135',
  '27136-27391',
  '27648-27903',
  '27904-28159',
  '28416-28671',
  '29184-29439',
  '29952-30207',
  '30976-31231',
  '32512-32767',
  '33280-33535',
  '33536-33791',
  '34304-34559',
  '39424-39679',
  '8192-8447',
  '8448-8703',
  'cjk-common-0',
  'cjk-common-1',
  'cjk-common-10',
  'cjk-common-11',
  'cjk-common-12',
  'cjk-common-13',
  'cjk-common-14',
  'cjk-common-15',
  'cjk-common-2',
  'cjk-common-3',
  'cjk-common-4',
  'cjk-common-5',
  'cjk-common-6',
  'cjk-common-7',
  'cjk-common-8',
  'cjk-common-9' ]

The scripts assume we split up the cjk-common PBF into chunks of 256. It looks like you will want most if not all of these 4096 characters as a baseline, always, all the time (if you run the script with 1 or 2 tiles alone you will often end up with 12-16 of the common ranges). You basically end up grabbing the common characters no matter what.

So combining the common glyphs into a single pack and eliminating the non cjk ranges from the list to reduce noise, we're down to:

osm (8 ranges)
[ '20224-20479',
  '20992-21247',
  '28416-28671',
  '29440-29695',
  '29952-30207',
  '33536-33791',
  '38912-39167',
  'cjk-common' ]

modern (15 ranges)
[ '22272-22527',
  '26880-27135',
  '27136-27391',
  '27648-27903',
  '27904-28159',
  '28416-28671',
  '29184-29439',
  '29952-30207',
  '30976-31231',
  '32512-32767',
  '33280-33535',
  '33536-33791',
  '34304-34559',
  '39424-39679',
  'cjk-common' ]

Conclusion + questions

Overall having a cjk-common glyph that takes precedence if a character falls into a fixed list of n (I picked 4096 based on a few runs -- 3000 not enough, 5000 has diminishing returns) looks like a good approach. You'll have most commonly used characters loaded and cached and will fire off requests as normal for other ranges as you hit less common characters.

The discrepancy between OSM's top characters and other analysis' top characters is worth some study though. Note that once we set this list changing it is very painful. It will affect any implementations using these endpoints and likely means we need to spec and version any endpoints around this strictly.

• "Place language" differs from normal usage significantly in english, german, etc. This is likely (?) the case for Chinese as well and could lead to this discrepancy.
• OSM data quality in China is an unknown to me. Setting a list of character frequency list based on the current state of OSM could be a bad idea without some overall confidence in current OSM data in China being representative of Chinese-language maps as a whole and future OSM data/map data.

Next actions

• Similar analysis for Hangul
• Branch of fontserver that can generate a PBF from a charlist rather than a start/end range,
• Branch of llmr that uses a cjk charlist to request the common CJK PBF and fallback to normal range glyphs otherwise,
• Test IRL
• Consult/further research on chinese char freq questions

cc @mikemorris @kkaefer @ansis @nickidlugash

Start with spec/fixtures/ and the cjk-osm.json and cjk-modern.json frequency data, then review the completed fontserver charlist branch and the remaining llmr and IRL-test actions. Done means deciding the CJK common-character approach, implementing the outstanding request/fallback work, and validating it with real-world tests and further frequency research.