[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <22432008.194c.197baceeae8.Coremail.00107082@163.com>
Date: Sun, 29 Jun 2025 16:30:12 +0800 (CST)
From: "David Wang" <00107082@....com>
To: musl@...ts.openwall.com
Subject: Re:Paintcans for reverse iterating strings
At 2025-06-29 08:08:43, "Rich Felker" <dalias@...c.org> wrote:
>One thing we're going to need for LC_COLLATE in locales where
>second-level weights are applied in reverse order (diacritic marks
>later in the string weigh more than earlier ones) is the ability to
>traverse (& live transform to NFD) the input string in reverse.
>
>In order not to take quadratic time doing this, we need a strategy for
>laying down a logarithmic (thus bounded by a small constant) number of
>waypoints ("paintcans") we can resume forward-processing at to
>simulate reverse-order random access.
>
Hi,
Maybe some mumbo jumbo, (I have no knowledge of LC_COLLATE, just takes it an interesting algorithm problem),
but is it possible to build a "small" finite state machine with "deterministic reverse transformations"
for all the "diacritic marks"?
If that possible, first iterating forward and keep state for each "diacritic marks", and
when reverse iterating string, a reverse state transformation can be carried out, maybe for each "diacritic marks"
, or could be only for current "diacritic marks".
(But this does not work for "random" access)
David
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
