Re: URL internationalization!

On Sun, 6 Apr 1997, Masataka Ohta wrote:

> > Got it. Also got a paper copy of it, in the proceedings of
> > last year's workshop. Terse and criptic writing, as always
> > in your case.
> 
> Apparently, you know nothing about formal language theory.

I know enough to understand the issues.

> The paper assumes that the readers have some knowledge on the
> difference between finite state automaton and push down automaton.

Yet it doesn't give a single reference on these topics!
Nor does it mention such an assumption.


> > Interestingly enough,
> > things such as Boyer-Moore work extremely well with UTF-8,
> > but fail quickly for iso 2022.
> 
> "Fail quickly"? What do you mean?

I don't mean the theoretical difficulties, but the practical
difficulties of setting up an expression for example to
capture a ü (in HTML notation) in a general ISO 2022
text (with bells and whistles such as designations and
invocations, and several coded character sets that contain
that character).


> Boyer-Moore is just determinization of finite-state automaton
> and works perfectly fine over any text with finite-state
> structure, including ISO 2022 based ones.
> 
> Boyer-Moore does not work at all with structured text with
> nesting.

If you want to stay on the theoretical side, then please
note that the BIDI nesting structure in Unicode is limited
to 16 levels. It is easy to construct an FSA, and possible
(although tedious) to construct a regular expression, for
limited levels of nesting. It is only for unlimited levels
of nesting that you need a push down automaton.

In addition, as long as you are searching logically
(which is what a user usually does), you can completely
ignore the BIDI nesting structure. It's similar to
looking for ASCII in an 8-bit ISO 2022 environment
where you are sure that nothing else except ASCII
ever gets designated/invoked into GL.

Also, it is similar to the situation where you search
for e certain variable name (or whatever) in a C program.
C can have a lot of nesting, but it is irrelevant for
all kinds of practical searching.

So on average, a regular expression to find a Hebrew
or Arabic word or character will be shorter for UTF-8
than for ISO 2022.

> > > Wrong. Conversion between logical and visual order needs
> > > push down automaton.
> > 
> > That is fine.
> 
> No.

Why not? What's so bad about it when we have to do a lot
of other processing for Arabic and Indic scripts anyway?
And if we really stay with it, as long as there is a bound
on the line length (such as 80 or 132 positions), the conversion
from logical to visual order could indeed be processed by
a finite series of replacing regular expressions, even
including what you call styled text, i.e. text that
doesn't fit on a line and where linebreaks have to be
found.


> > It only affects one step, namely the display of
> > URLs. And it actually helps all the rest, because if we can
> > use logical order internally, things such as searching, relative
> > URL processing, sorting, and so on, will work nicely without any
> > changes.
> 
> Searching with push down automaton is a lot lot lot more slower
> (O(N**3)) than searching with finite state machines.
> 
> The more serious problem is that there is no handy notation,
> such as regular expression of finite state search, of search
> patterns.

Thanks for giving us the theoretical results. But as explained
above, we don't need puth down automata for searching in UTF-8.
And here is another interesting tidbit from the recent workshop
in Tsukuba: Mark Crispin told us about an extension to the IMAP
protocol to do search in messages. When asked who this would be
implemented, he told us about one (at the moment the only)
implementation, which converted everything to UTF-8. Obviously,
with real implementations, practical facts count more than
theoretical ramblings.


> > For UTF-8, there is no need to do any external/internal
> > conversion for comparison, you can use a lot of your
> > favorit UNIX tools on it directly.
> 
> Martin, you are biting yourself.

What do you mean? You stated how important it is to use
these tools. I explained that with UTF-8, it is actually
easier than with ISO 2022. The home of most of the ideas
on UNIX tools, the Bell Labs, is actually also the home
of UTF-8. If they wouldn't have been able to use the tools
they cared and liked, they wouldn't have introduced UTF-8.


> Though you said:
> 
> > in your case. And rather blatant inconsistencies, such as
> > on the one hand saying that grep is very important, and on
> 
> I never said "grep is very important". I said:
> 
> 	First of all, many text processing tools depend on regular
> 	expression.
> 	Plain text on which UNIX "grep" can't be applicable is not
> 	so meaningful.
> 
> Not only grep but also all the UNIX and non-UNIX plain text
> processing tools of some complexity, rely on regular expressions.

Sorry for generalizing a little bit with "grep is very important".
You never generalize, don't you :-)?

Regards,	Martin.