GeezerVison is showing github.com — Add unicode grapheme cluster break algorithm · Issue #74902 · python/cpython
Add unicode grapheme cluster break algorithm #74902Description
| BPO |
30717 |
| Nosy |
@malemburg, @loewis, @terryjreedy, @scoder, @vstinner, @benjaminp, @jwilk, @mcepl, @ezio-melotti, @stevendaprano, @bitdancer, @methane, @serhiy-storchaka, @jenstroeger, @zhangyangyu, @pganssle, @Vermeille, @bertjwregeer, @bianjp, @Manishearth |
| PRs |
gh-74902: add unicode grapheme cluster break algorithm #2673 |
Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.
Show more details
GitHub fields:
assignee = None
closed_at = None
created_at = <Date 2017-06-20.19:15:22.212>
labels = ['interpreter-core', 'type-feature', '3.7', 'expert-unicode']
title = 'Add unicode grapheme cluster break algorithm'
updated_at = <Date 2021-06-29.16:33:48.790>
user = 'https://github.com/Vermeille' bugs.python.org fields:
activity = <Date 2021-06-29.16:33:48.790>
actor = 'jwilk'
assignee = 'none'
closed = False
closed_date = None
closer = None
components = ['Interpreter Core', 'Unicode']
creation = <Date 2017-06-20.19:15:22.212>
creator = 'Guillaume Sanchez'
dependencies = []
files = []
hgrepos = []
issue_num = 30717
keywords = []
message_count = 27.0
messages = ['296478', '296479', '296503', '296504', '296505', '297488', '298190', '298321', '298325', '298326', '298336', '299661', '299699', '299703', '299706', '299707', '299708', '299731', '299734', '299848', '312035', '359397', '359398', '359408', '359409', '359450', '359496']
nosy_count = 22.0
nosy_names = ['lemburg', 'loewis', 'terry.reedy', 'scoder', 'vstinner', 'benjamin.peterson', 'jwilk', 'mcepl', 'ezio.melotti', 'mrabarnett', 'steven.daprano', 'r.david.murray', 'methane', 'serhiy.storchaka', '_savage', 'xiang.zhang', 'p-ganssle', 'Socob', 'Guillaume Sanchez', 'Bert JW Regeer', 'bianjp', 'Manishearth']
pr_nums = ['2673']
priority = 'normal'
resolution = None
stage = 'patch review'
status = 'open'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue30717'
versions = ['Python 3.7'] Linked PRs
Reacted by Matthieu LAURENT, Álvaro Mondéjar Rubio and Santiago Fraire Willemoes ActivityVermeille commented on Jun 20, 2017 MannequinAuthor More actions "a⃑".center(width=5, fillchar=".")
produces
'..a⃑.' instead of '..a⃑..'
The reason is that "a⃑" is composed of two code points (2 UCS4 chars), one 'a' and one combining code point "above arrow". str.center() counts the size of the string and fills it both sides with fillchar until the size reaches width. However, this size is certainly intended to be the number of characters and not the number of code points.
The correct way to count characters is to use the grapheme clustering algorithm from UAX TR29.
Turns out I implemented this myself already, and might do the PR if asked so, with a little help to make the C <-> Python glue.
Thanks for your time. Vermeille commented on Jun 20, 2017 MannequinAuthor More actions Obviously, I'm talking about str.center() but all functions needing a count of graphemes are then not totally correct.
I can fix that and add the corresponding function, or an iterator over graphemes, or whatever seems right :) stevendaprano commented on Jun 21, 2017 I don't think graphemes is the right term here. Graphemes are language dependent, for instance "dž" may be considered a grapheme in Croatian.
https://en.wikipedia.org/wiki/D%C5%BE
http://www.unicode.org/glossary/#grapheme
I believe you are referring to combining characters:
http://www.unicode.org/faq/char_combmark.html
It is unfortunate that Python's string methods are naive about combining characters, and just count code points, but I'm not sure what the alternative is. For example the human reader may be surprised that these give two different results:
py> len("naïve")
5
py> len("naïve")
6I'm not sure if the effect will survive copying and pasting, but the first string uses
U+00EF LATIN SMALL LETTER I WITH DIAERESIS
while the second uses:
U+0069 LATIN SMALL LETTER I + U+0308 COMBINING DIAERESIS
And check out this surprising result:
It seems to me that it would be great if Python was fully aware of combining characters, its not so great if it is naïve, but it would be simply terrible if only a few methods were aware and the rest naïve.
I don't have a good solution to this, but perhaps an iterator over (base character + combining marks) would be a good first step. Something like this?
import unicodedata
def chars(string):
accum = []
for c in string:
cat = unicodedata.category(c)
if cat == 'Mn':
accum.append(c)
else:
if accum:
yield accum
accum = []
accum.append(c)
if accum:
yield accumVermeille commented on Jun 21, 2017 MannequinAuthor More actions Thanks for all those interesting cases you brought here! I didn't think of that at all!
I'm using the word "grapheme" as per the definition given in UAX TR29 which is *not* language/locale dependant [1].
This annex is very specific and precise about where to break "grapheme cluster" aka "when does a character starts and ends". Sadly, it's a bit more complex than just accumulating based on the Combining property. This annex gives a set of rules to implement, based on Grapheme_Cluster_Break property, and while those rules may naively be implemented as comparing adjacent pairs of code points, this is wrong and can be correctly and efficiently implemented as an automaton. My code [2] passes all tests from GraphemeBreakTests.txt (provided by Unicode).
We can definitely do a generator like you propose, or rather do it in the C layer to gain more efficiency and coherence since the other string / Unicode operations are in the C layer (upper, lower, casefold, etc)
Let me know what you guys think, what (and if) I should contribute :)
[1] http://www.unicode.org/reports/tr29/#Grapheme_Cluster_Boundaries
[2] https://github.com/Vermeille/batriz/blob/master/src/str/grapheme_iterator.h#L31 stevendaprano commented on Jun 21, 2017 http://www.unicode.org/reports/tr29/#Grapheme_Cluster_Boundaries
talks about *grapheme clusters*, not "graphemes" alone, and it seems clear to me that they are language dependent. For example, it says:
The Unicode Standard provides default algorithms for determining grapheme cluster boundaries, with two variants: legacy grapheme clusters and extended grapheme clusters. The most appropriate variant depends on the language and operation involved. ... These algorithms can be adapted to produce tailored grapheme clusters for specific locales...
Nevertheless, even just a basic API to either the *legacy grapheme cluster* or the *extended grapheme cluster* algorithms would be a good start.
Can I suggest that the unicodedata module might be the right place for it?
And thank you for volunteering to do the work on this! bitdancer commented on Jul 1, 2017 Vermeille commented on Jul 11, 2017 MannequinAuthor More actions Hello to all of you, sorry for the delay. Been busy.
I added the base code needed to built the grapheme cluster break algorithm. We now have the GraphemeBreakProperty available via unicodedata.grapheme_cluster_break()
Can you check that the implementation correctly fits the design? I was not sure about adding that prop to unicodedata_db ou unicodectype_db, tbh.
If it's all correct, I'll move forward with the automaton and the grapheme cluster breaking algorithm.
Thanks! Vermeille commented on Jul 13, 2017 MannequinAuthor More actions Hello,
I implemented unicodedata.break_graphemes() that returns an iterators that spits consecutive graphemes.
This is a "test" implementation meant to see what doesn't fits Python's style and design, to discuss naming and implementation details.
#2673
Thanks for your time and interest stevendaprano commented on Jul 14, 2017 Thank you, but I cannot review your C code.
Can you start by telling us what the two functions:
unicodedata.grapheme_cluster_break()
unicodedata.break_graphemes() take as arguments, and what they return? If we were to call
help(function), what would we see? Vermeille commented on Jul 14, 2017 MannequinAuthor More actions Hello Steven!
Thanks for your reactivity!
unicodedata.grapheme_cluster_break() takes a unicode code point as an argument and return its GraphemeBreakProperty as a string. Possible values are listed here: http://www.unicode.org/reports/tr29/#CR
help(unicodedata.grapheme_cluster_break) says:
grapheme_cluster_break(chr, /)
Returns the GraphemeBreakProperty assigned to the character chr as string.
====
unicodedata.break_graphemes() takes a unicode string as argument and returns an GraphemeClusterIterator that spits consecutive graphemes clusters.
help(unicodedata.break_graphemes) says:
break_graphemes(unistr, /)
Returns an iterator to iterate over grapheme clusters in unistr.
It uses extended grapheme cluster rules from TR29.
Is there anything else you would like to know? Don't hesitate to ask :)
Thank you for your time! serhiy-storchaka commented on Dec 22, 2025 Since there were too many differences from #2673, I created a new PR #143076. The main differences:
- It encodes the rules in the code instead of using a state machine. The old state machine no longer works with the recent Unicode (since 11.0.0), and I do not know how it was created at first place. If in future we will switch to a state machine, it should be generated from human readable rules, not taken from unknown source.
- The iterators emits not strings, but objects which have
start and end attributes. They can bee converted to string to get the corresponding string.
- Exposed other properties related to the algorithm in
unicodedata.
- Added tests and documentation.
serhiy-storchaka commented on Dec 22, 2025 I also moved the state of the iterator to a separate structure. It can help when implementing unicodedata.width() which will be able to break the string on graphemes without an addition overhead.
MetadataMetadataDevelopmentNo branches or pull requestsIssue actions
|