Subject: Memory required for Input Method

From: "L.S.Ng" <[email-masked]>
Date: Fri, 18 Mar 1994 23:35:10 GMT

Memory is a big concerned for writing 'very small Chinese programs'.
Chinese programs are notorious for memory-hungry. Two components consume
a lot of memory, i.e. the font and the dictionary (or Input Method).

The minimum memory required by a decent input method is about 60K.
Consider the specific case of character base input method, which is
decent, time-tested (read old) and reliable. A typical input sequence of
a few keys is normally compressed to a long int (4-byte). [ in Eten, to
save memory, it implements a special data type of 3-byte long ]. There
will be 94*94 (or less) of them in Guobiao code. The total number of
bytes required by the dictionary file is therefore  35344 bytes. But
normally only 6768 bytes (Non-symbol Character) are used. So it would be
27072 byte.

To search the dictionary effectively, a binary tree needs to be
maintained.

(A deviation from the discussion: YG Zhang implemeted the search tree in
what he called 'trie', which is a multinode tree. I eventually found
that it is IMPOSSIBLE to be implemented on DOS machine because of its
sheer size, >> 640K. He did it on Unix. :-) Also what can be done by
multinode tree can be done by binary tree with a minimum requirement of
42K memory.)

The size of a binary tree is the CODE SPACE (6768) times the size of
each node. Suppose each node contained three 16-bits pointers, i.e.
left, right, self, then the tree size would be about 7000*6 = 42K. This
assumes the dictionary size is less than 64K, else 32 bits pointer would
be required, which makes the tree node twice as large.

So the total size is 42K + 28K = 60K.

For the so called 'intelligent' input method like phrase input, the
memory required is much more than that. Firstly the dictionary file
would be larger than 64K anyway, and the CODE SPACE is not limited to
7000, it is as many as the number of phrases in the dictionary. Two
times 60K would be a rough estimate.

Sincerely,
Liangsheng WU