By Rami Gabai
June 16th, 2005
The purpose of the BiDi algorithm is to rearrange text presentation for JavaScript or flash application, to match Right-to-left text lines correctly.
The basic idea is to map the words in each line to 3 different identifiers, and rearrange the words in related groups, while solving local difficulties by using state-machine.
Algorithm implementation was tested in JavaScript and Java and managed to work correctly in all tests.
This is done in 3 stages, as now described:
1. Pre-Processing
>> Input: Text string
Scan text line. Divide it to words. Each word is an object with properties of text (String), mapping (Integer).
Each word can get a mapping of R (Right-to-left word), L (Left-to-right word), or N (Neutral word/character). A word mapped as N, containing more than one concurrent N-mapped characters, is divided into single character words (mapped as N).
>> Output: Array of words
2. Reordering Words
>> Input: Array of words
Implemented as finite state machine.
Four possibilities in each state (N, L, R, ε = nothing)
(1) Join Current Set
(2) Break Current Set
>> Output: Reordered Array of words
3. Post-Processing
>> Input: Reordered Array of words
Scan Right side of array until you find a R-mapped word.
For all words until then if it is a N-mapped word rotate this word.
Scan Left side of array until you find a R-mapped word.
For all words until then if it is a N-mapped word rotate this word.
(Ex: turn ']' to '[').
Reverse the order of the words in the array.
Create a string text from the reversed order of words.
>> Output: Array of words
