What's going on
We are concerned with establishing a 1-to-1 association between the strings of two languages. One language, call it Ll, consists of all the finite non-empty sequences of characters from some alphabet S0. The other language, call it Ls, consists of all the finite non-empty sequences of characters drawn from S1 (where S1 ‚ S0) that begin with a character from S2 (S2 ‚ S1). We want some restrictions on the association. We want the association to basically have the form of a bunch of (literal) pattern replacements --- that is, where pattern a appears in the string in Ll, pattern b appears in the string in Ls, for a bunch of client-specified a and b.
The technique used is as follows. Ignore for the moment the restriction on the initial character of a string in Ls --- we'll translate from Ll to Lm, where Lm = S1+, then make a seperate step from Lm to Ls.
For getting from Ll to Lm, we restrict the a's to be single characters. Identify in S1 an "escape character" y. Define a substitution function q, which associates with every character c in S0- (where S0- = S0-S1) a unique string b in S1-+ (where S1- = S1-{y}, and + means a non-empty finite string thereof). Let B be the range of q. The relation is as follows: ync in a string in Ll maps to y2n+1b in Lm when c S0- and q(c)=b. ynb maps to y2nb when b B and to ynb otherwise; b must contain only characters from S1-.
To translate sm (in Lm) to ss (in Ls), pick another escape character (call it f), this time from S2. Scan sm and find the first character (call it d) that's not f. If you run out of string, or if d S2, then ss = sm; otherwise ss = fsm.
Now we do it precisely.
Given
S2 ‚ S1 ‚ S0
y S1, f S2
q: S0- é B
Where
S0- = S0 - S1
S1- = S1 - {y}
Ll = S0+
Lm = S1+
Ls = S2 S1*
B ‚ S1-+
B has the prefix property:
b1, b2 B : b1 ` b2 Ò ¬ IsPrefix(b1, b2)
N is the non-negative integers
e is the empty string
Define
Code(ss, sl) { sm Lm Shrink(sm, sl) ' Initialize(ss, sm)
Shrink(sm, sl) {
if sm=e ' sl=e then true
else if n N, c S0-, slr S0* sl = yncslr
then smr Lm sm = y2n+1q(c)smr ' Shrink(smr, slr)
else if n N, b B, slr S0* sl = ynbslr
then smr Lm sm = y2nbsmr ' Shrink(smr, slr)
else if n N, b S1-*, slr S0* sl = ynbslr ' Best(b, slr)
then smr Lm sm = ynbsmr ' Shrink(smr, slr)
else false
Best(b, slr) {means b is as long as it can be} {
slr=e
( b`e ' slrr Ll slr = yslrr
( c S0-, slrr Ll slr = cslrr
Initialize(ss, sm) {
Verboten(sm) ' ss=fsm ( ¬Verboten(sm) ' ss=sm
Verboten(s) = n N, c S1 - S2, sr S1* s = fncsr
Auf Cedar
StringNotInLanguage: ERROR [s: ROPE, L: Language];
ROPE: TYPE = Rope.ROPE;
CreateCode: PROC [membership: Membership, y, f: CHAR, q: SubstitutionFunction] RETURNS [code: Code];
Membership: TYPE = ARRAY CHAR OF Alphabet;
Alphabet: TYPE = {S0, S1, S2, None};
SubstitutionFunction: TYPE = ARRAY CHAR OF ROPE;
Language: TYPE = {Ll, Ls, Lm};
Code: TYPE = REF CodePrivate;
CodePrivate: TYPE;
Encode: PROC [code: Code, sl: ROPE] RETURNS [ss: ROPE];
Decode: PROC [code: Code, ss: ROPE] RETURNS [sl: ROPE];
Lowercase: PROC [r: ROPE] RETURNS [lr: ROPE];