Fwd: Visual to Logical Order

--===============1988792529==
Content-Type: multipart/alternative; boundary=001a11c322f6beb8c60526504875

--001a11c322f6beb8c60526504875
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

It's funny, we humans run this non-existant algorithm all the time; the
sole purpose of UAX 9 and FriBidi is feeding more inputs to our Vis2Log
algo :-)

Some thoughts:

- Do you know base direction?  Autodetecting it from visual input is harder
than from logical.
  E.g. "he said EMBEDDING" and "HE SAID embedding" both look like "ltr RTL"
visually.
  Percentage might work better than first-strong.
  Dangling punctuation at one end =E2=80=94 especially .?! =E2=80=94 may be=
 a quite robust
sign, if present.

- If the visual input has any markup/formatting, translating all structure
into FSI..PDI should help.

- Do you have line breaks?  It feels to me the per-line reordering should
complicate reassembly and log2vis can not work well on split lines.
  Though experimenting with "bidiv -w 10" I have trouble finding any
problematic example, so it's probably not severe...
  OK, got one with numbers:

# The first `bidiv -w $w` generates visual data with line splits (can't use
`fribidi --caprtl` because it still wrongly does line wrapping after
reordering).
# The second `bidiv` approximates vis2log; can be replaced with `fribidi
--ltr --nopad` with exactly same results.

$ for w in $(seq 15); do
    echo 'foo bar BAZ 123456789 QUUX they said' | perl -C -pe 'use utf8;
tr/A-Z/=D7=90-=D7=A9/' |
      bidiv -j -w $w |
      bidiv -j |
      perl -C -pe 'use utf8; tr/=D7=90-=D7=A9/A-Z/' | tr -d '\n'
    echo "  # -w $w"
done
foo bar BAZ 123456789 QUUX they said  # -w 1
foo bar BAZ 123456789 QUUX they said  # -w 2
foo bar BAZ 123456789 QUUX they said  # -w 3
foo bar BAZ 123456789 QUUX they said  # -w 4
foo bar BA123 Z456789 QUUX they said  # -w 5
foo bar BAZ 123456789 QUUX they said  # -w 6
foo bar 12 BAZ3456789 QUUX they said  # -w 7
foo bar 1234 BAZ56789 QUUX they said  # -w 8
foo bar B123456 AZ789 QUUX they said  # -w 9
foo bar BA12345678 Z9 QUUX they said  # -w 10
foo bar BAZ 123456789 QUUX they said  # -w 11
foo bar BAZ 123456789 QUUX they said  # -w 12
foo bar 1 BAZ23456789 QUUX they said  # -w 13
foo bar 12 BAZ3456789 QUUX they said  # -w 14
foo bar 123 BAZ456789 QUUX they said  # -w 15

As can be expected, joining the lines (`tr -d '\n'`) before the second
"vis2log" bidiv makes things worse e.g. XQUU 456789Z 123BA.
Per-line reordering can make contiguous text non-contiguous and deleting
the break points definitely looses data in way that'd be hard even for
AI-complete humans.

[resending as first try from non-subscribed address was rejected, sorry if
you get it twice]

2015-11-14 20:47 GMT+02:00 Dov Grobgeld <[email protected]>:

> Hi Hossein,
>
> Currently there is no algorithm in fribidi doing visual to logical, and a=
s
> you said in general this inversion cannot be done. A first guess would be
> just to do logical to visual on the visual string.
>
> A better approch would be something similar to the following:
>
> 1. Let's call the algorithm doing L=E2=86=92V convertion V(s), i.e.
> fribidi_log2vis() in fribidi, and v the visual string and s the logical
> string.
> 2. Make an initial guess of the logical string s_0 =3D V(v).
> 3. While V(s_i) =E2=89=A0 s: modify s_{i+1}=3DM(s_i) and try again.
>
> This basically turns the problem into a problem of how to write the
> modification function M(s). This may probably be done by comparing V(s) a=
nd
> v and using the differences between them to move misplaces characters to
> the other side of L and R boundaries.
>
> Another idea would be to check out the algorithm in the ICU sources. Or t=
o
> ask the lead ICU author if he could provide some references to the
> heuristics they used.
>
> Regards,
> Dov
>
>
>
>
>
> On Sat, Nov 14, 2015 at 4:18 AM, Hossein Khatoonabadi <
> [email protected]> wrote:
>
>> Hi / Dorood,
>>
>> I'm looking for a function that converts a visual context to a logical
>> string using FiriBidi library.
>>
>> I know that there is no standard algorithm for this, and there is no
>> unique answer. However, ICU has a function that approximates logical fro=
m
>> visual order. I've read the FiriBidi mailing list regarding this topic
>> (from couple of years ago), but there was no acceptable
>> conclusion/workaround at the time.
>>
>> It has been years now since that discussion and I'm sure many like us ar=
e
>> still looking for such a function. Does anyone have any idea?
>>
>>

--001a11c322f6beb8c60526504875
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div class=3D"gmail_quote"><div dir=3D"ltr"><div>It&#39;s =
funny, we humans run this non-existant algorithm all the time; the sole pur=
pose of UAX 9 and FriBidi is feeding more inputs to our Vis2Log algo :-)<br=
></div><div><br></div><div>Some thoughts:</div><div><br></div><div>- Do you=
 know base direction?=C2=A0 Autodetecting it from visual input is harder th=
an from logical.</div><div>=C2=A0 E.g. &quot;he said EMBEDDING&quot; and &q=
uot;HE SAID embedding&quot; both look like &quot;ltr RTL&quot; visually.</d=
iv><div>=C2=A0 Percentage might work better than first-strong.</div><div>=
=C2=A0 Dangling punctuation at one end =E2=80=94 especially .?! =E2=80=94 m=
ay be a quite robust sign, if present.</div><div><br></div><div>- If the vi=
sual input has any markup/formatting, translating all structure into FSI..P=
DI should help.<br></div><div><br></div><div>- Do you have line breaks?=C2=
=A0 It feels to me the per-line reordering should complicate reassembly and=
 log2vis can not work well on split lines.</div><div>=C2=A0 Though experime=
nting with &quot;bidiv -w 10&quot; I have trouble finding any problematic e=
xample, so it&#39;s probably not severe...=C2=A0</div><div>=C2=A0 OK, got o=
ne with numbers:</div><div><br></div><div># The first `bidiv -w $w` generat=
es visual data with line splits (can&#39;t use `fribidi --caprtl` because i=
t still wrongly does line wrapping after reordering).</div><div># The secon=
d `bidiv` approximates vis2log; can be replaced with `fribidi --ltr --nopad=
` with exactly same results.</div><div><br></div><div><div>$ for w in $(seq=
 15); do=C2=A0</div><div>=C2=A0 =C2=A0 echo &#39;foo bar BAZ 123456789 QUUX=
 they said&#39; | perl -C -pe &#39;use utf8; tr/A-Z/=D7=90-=D7=A9/&#39; |=
=C2=A0</div><div>=C2=A0 =C2=A0 =C2=A0 bidiv -j -w $w |=C2=A0</div><div>=C2=
=A0 =C2=A0 =C2=A0 bidiv -j |=C2=A0</div><div>=C2=A0 =C2=A0 =C2=A0 perl -C -=
pe &#39;use utf8; tr/=D7=90-=D7=A9/A-Z/&#39; | tr -d &#39;\n&#39;</div><div=
>=C2=A0 =C2=A0 echo &quot; =C2=A0# -w $w&quot;</div><div>done</div><div>foo=
 bar BAZ 123456789 QUUX they said =C2=A0# -w 1</div><div>foo bar BAZ 123456=
789 QUUX they said =C2=A0# -w 2</div><div>foo bar BAZ 123456789 QUUX they s=
aid =C2=A0# -w 3</div><div>foo bar BAZ 123456789 QUUX they said =C2=A0# -w =
4</div><div>foo bar BA123 Z456789 QUUX they said =C2=A0# -w 5</div><div>foo=
 bar BAZ 123456789 QUUX they said =C2=A0# -w 6</div><div>foo bar 12 BAZ3456=
789 QUUX they said =C2=A0# -w 7</div><div>foo bar 1234 BAZ56789 QUUX they s=
aid =C2=A0# -w 8</div><div>foo bar B123456 AZ789 QUUX they said =C2=A0# -w =
9</div><div>foo bar BA12345678 Z9 QUUX they said =C2=A0# -w 10</div><div>fo=
o bar BAZ 123456789 QUUX they said =C2=A0# -w 11</div><div>foo bar BAZ 1234=
56789 QUUX they said =C2=A0# -w 12</div><div>foo bar 1 BAZ23456789 QUUX the=
y said =C2=A0# -w 13</div><div>foo bar 12 BAZ3456789 QUUX they said =C2=A0#=
 -w 14</div><div>foo bar 123 BAZ456789 QUUX they said =C2=A0# -w 15</div></=
div><div><br></div><div>As can be expected, joining the lines (`tr -d &#39;=
\n&#39;`) before the second &quot;vis2log&quot; bidiv makes things worse e.=
g. XQUU 456789Z 123BA.<br></div><div>Per-line reordering can make contiguou=
s text non-contiguous and deleting the break points definitely looses data =
in way that&#39;d be hard even for AI-complete humans.</div><div><br></div>=
<div>[resending as first try from non-subscribed address was rejected, sorr=
y if you get it twice]<br></div></div><div><div><div class=3D"gmail_extra">=
<br><div class=3D"gmail_quote">2015-11-14 20:47 GMT+02:00 Dov Grobgeld <spa=
n dir=3D"ltr">&lt;<a href=3D"mailto:[email protected]" target=3D"_blan=
k">[email protected]</a>&gt;</span>:<br><blockquote class=3D"gmail_quo=
te" style=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-col=
or:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir=3D"l=
tr"><div style=3D"font-family:arial,helvetica,sans-serif">Hi Hossein,<br><b=
r></div><div style=3D"font-family:arial,helvetica,sans-serif">Currently the=
re is no algorithm in fribidi doing visual to logical, and as you said in g=
eneral this inversion cannot be done. A first guess would be just to do log=
ical to visual on the visual string. <br><br>A better approch would be some=
thing similar to the following:<br><br></div><div style=3D"font-family:aria=
l,helvetica,sans-serif">1. Let&#39;s call the algorithm doing L=E2=86=92V c=
onvertion V(s), i.e. fribidi_log2vis() in fribidi, and v the visual string =
and s the logical string.<br></div><div style=3D"font-family:arial,helvetic=
a,sans-serif">2. Make an initial guess of the logical string s_0 =3D V(v).<=
br></div><div style=3D"font-family:arial,helvetica,sans-serif">3. While V(s=
_i) =E2=89=A0 s: modify s_{i+1}=3DM(s_i) and try again.<br><br></div><div s=
tyle=3D"font-family:arial,helvetica,sans-serif">This basically turns the pr=
oblem into a problem of how to write the modification function M(s). This m=
ay probably be done by comparing V(s) and v and using the differences betwe=
en them to move misplaces characters to the other side of L and R boundarie=
s. <br><br></div><div style=3D"font-family:arial,helvetica,sans-serif">Anot=
her idea would be to check out the algorithm in the ICU sources. Or to ask =
the lead ICU author if he could provide some references to the heuristics t=
hey used.<br><br></div><div style=3D"font-family:arial,helvetica,sans-serif=
">Regards,<br></div><div style=3D"font-family:arial,helvetica,sans-serif">D=
ov<br></div><div style=3D"font-family:arial,helvetica,sans-serif"><br><br><=
/div><div style=3D"font-family:arial,helvetica,sans-serif"><br><br></div></=
div><div class=3D"gmail_extra"><br><div class=3D"gmail_quote"><div><div>On =
Sat, Nov 14, 2015 at 4:18 AM, Hossein Khatoonabadi <span dir=3D"ltr">&lt;<a=
 href=3D"mailto:[email protected]" target=3D"_blank">hkhatoonabadi@=
pdftron.com</a>&gt;</span> wrote:<br></div></div><blockquote class=3D"gmail=
_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left=
-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div><div=
><div dir=3D"ltr">Hi / Dorood,<div><br></div><div>I&#39;m looking for a fun=
ction that converts a visual context to a logical string using FiriBidi lib=
rary.=C2=A0</div><div><br></div><div>I know that there is no standard algor=
ithm for this, and there is no unique answer. However, ICU has a function t=
hat approximates logical from visual order. I&#39;ve read the FiriBidi mail=
ing list regarding this topic (from couple of years ago), but there was no =
acceptable conclusion/workaround at the time.=C2=A0</div><div><br></div><di=
v>It has been years now since that discussion and I&#39;m sure many like us=
 are still looking for such a function. Does anyone have any idea?</div><di=
v><br></div></div></div></div></blockquote></div></div></blockquote></div><=
/div></div></div></div><br></div>

--001a11c322f6beb8c60526504875--

--===============1988792529==
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: base64
Content-Disposition: inline

X19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX18KZnJpYmlkaSBt
YWlsaW5nIGxpc3QKZnJpYmlkaUBsaXN0cy5mcmVlZGVza3RvcC5vcmcKaHR0cDovL2xpc3RzLmZy
ZWVkZXNrdG9wLm9yZy9tYWlsbWFuL2xpc3RpbmZvL2ZyaWJpZGkK

--===============1988792529==--