PISIT' S THAI NATURAL LANGUAGE PROCESSING LABORATORY
This lab is formed since August 26, 1998
e-mail: [email protected]
For C7 members, please check this C7 address list.
KEYWORDS
Thai Natural Language Processing Lab., words
segmentation, dictionaries, algorithms, Thai text-to-speech.
�ç���ҧ�����ž��ҹء��Ẻ����
(Trie Data Structure)
����ǹ�
�ç���ҧ������Ẻ�������ç���ҧ�����ŷ�����������Ѻ�纾��ҹء������
���͡�õѴ�������� ����ͧ�Ҩҡ������Է���Ҿ�٧������ͧ�����Ǵ����㹡��
�ӧҹ��Ф��������Ѵ���ͷ��㹡�èѴ�红����ž��ҹء�� �͡�ҡ����ѧ����������Ѻ
��÷ӴѪ�����͡����鹢����Ũҡ��ͤ�������͡��â�Ҵ�˭� ���¤���ç���ҧ������
Ẻ��������ա�觡�ҹ (edges) ᷹����ѡ�÷����������繢������ � ����ͧ��èѴ�� [1] �
�óշ������¨Ѵ�红����ž��ҹء�� ��˹�觤ӡ����ҡ��鹷ҧ (Path) �ҡ�ҡ���仨�
�֧㺴ѧ������ҧ����¤
��С�����á������֡����¡��ҧ
��ͤ����ҡ������ҧ��ҧ����Сͺ���¤ӵ�ҧ � �ѧ���仹�� ���ѧࡵ����������ա��
�Ѵ���ѡ�÷������ǹ�鹫�ӡѹ����ͷӡ�èѴ�纴����ç���ҧ������Ẻ����
��......����
���.....���
�������.�����
���.....���
���.....���
��......��
��ҧ....�ҧ
¡......¡
�֡��...֡��
�����仨Ѵ����ç���ҧ������Ẻ���¨���ѧ�ٻ��ҧ��ҧ
������ҧ�ç���ҧ�����ŷ���
������ҧ�ç���ҧ������Ẻ�����Ҩ�������������� (Array) �������������
(Pointer) ���� 㹷��������ҧ���¡�����������Ẻ���·ҧ������˹��á���١���
�˹��Ѵ����١��дѺ���ǡѹ (First Child Next Sibling Multi way Tree) �ٻ��ҧ��ҧ���
������ҧ����Ẻ��������ѧ����Ǣͧ������ҧ�ҡ������ٻ��ҧ��
���ͧ�ҡ���¤���ç���ҧ������Ẻ�����ѧ��鹤����Ǵ����㹡�÷ӧҹ�������
�� O(log n) [2] ���ͤ�������㹡�÷ӧҹ �ռ��üѹ�����ҡ�Ѻ��Ҵ�ͧ�����Ũ֧��
������������Ѻ�����Ţ�Ҵ�˭��ҡ�����ç���ҧ������Ẻ�������� ����ԧ����ʵ����üѹ
�µç�Ѻ��Ҵ�����ŷ������ O(n) ������˹��ͧ�������������������繵�����ҧ��
��Сͺ仴��������ǹ��� ������ ������������ѧ�١����á (first child) ��о����������
�ѧ�١��ҧ��§ (next sibling) �˹��ͧ���´ѧ����ǹ������ö�ʴ���ѡɳС�ù�������
Ẻ���ҫ���ѧ���仹��
typedef struct trie_node *trie_ptr;
struct trie_node
{
element_type element;
trie_ptr first_child;
trie_ptr next_sibling;
}
�š�÷��ͧ���ҧ����
��ӡ�÷��ͧ��������ç���ҧ����������Ѻ������Ѵ�������� ��
������ѧ�����价ӡ�õѴ�ӡѺ�����š��������ͧ��Ѻ �ش�á��;���Ҫ�ѭ�ѵ�
�ͧ�ع�����ç�������á�ҧ�ѹ��ç���¹��ж��֡�Ҿ.�. �ͧ��������ҫ���բ�Ҵ
7,686 ����ѡ����Ъش����ͧ��ͪش�á����Ѻ����Ҫ�ѭ�ѵ��Է�ء�Ш�����§����Է����
��ȹ�.�. �ͧ������Ỵ ����բ�Ҵ��� 25,846 ����ѡ�� �·�衮���·���ͧ���Ҩҡ���
�������������ͧ��С�����á�ɮա� �����ӡ�÷��ͧ�Ѻ���ҹء�������ͧ�ش
�ªش�á��;��ҹء�����·���դ������㹡����ҹ㹪��Ե��Ш��ѹ�٧�բ�Ҵ 3,963
�� ����ա�ش�繾��ҹء�����·���仫���բ�Ҵ 17,859 �� ��ӡ����ػ�š�÷��ͧ
���㹵��ҧ��ҧ��ҧ�͡�ҡ����÷��ͧ�龺ʶԵԢͧ�ç���ҧ�����ŷ��·����ʹ������
仨Ѵ�纾��ҹء�������¤�;���Ҩҡ���ҹء���ش�á��ӹǹ�˹�������㹷���
�� 4,751 �˹� �ըӹǹ�˹���дѺ����ͧ (�дѺ�á����ҡ) �� 42 �˹� �դ�������
�ͧ�˹���дѺ�������� 17 ��Ф������¢ͧ�˹���дѺ� (leaf) �� 5 㹢�з��ҡ
���ҹء���ش����ͧ�������ӹǹ�˹�������㹷����� 18,952 �˹� �ըӹǹ�˹�
��дѺ����ͧ (�дѺ�á����ҡ) �� 48 �˹� �դ������¢ͧ�˹���дѺ�������� 21
��Ф������¢ͧ�˹���дѺ� (leaf) �� 17 ���������Ҥ�Ҩӹǹ�˹�����������
�дѺ�դ�������§�ѹ�֧���ӹǹ��㹾��ҹء����ҧ�ѹ�ҡ������˵ؼŷ�������������
㹡�÷ӧҹ����ҧ�������������ç���ҧ������Ẻ���¹�����ç���ҧ����������Ѻ
���ҹء��
�Ԩ�óҵ��ҧ�š�÷��ͧ��ҧ��ҧ�����������Ҵ���ҹء���ҡ 3,963 ����
17,859 �� ����������� 350% �������������ç���ҧ������Ẻ�������ҷ����㹡�õѴ��
������� 48% ��袹Ҵ������ 7,686 ����ѡ�� ���袹Ҵ������ 25,846 ����ѡ�� ���ҷ����
�ҹ������� 12% ���º��º�Ѻ�ç���ҧ������Ẻ�������������� 374% ��袹Ҵ������
3963 �� ���������� 383% ��袹Ҵ������ 25,846 ����ѡ��
�ҡ���ҧ���ǡѹ����������������Ҵ�����Ũҡ 7,686 ����ѡ���� 25,846 ���
�ѡ�� ����������� 236% ����Ҥ������Ǣͧ����������� 214% ��� 137% ��袹Ҵ
���ҹء���ӹǹ 3,963 �� ��� 17859 �� ����ӴѺ ���º��º�Ѻ�ç���ҧ������
Ẻ���������㹡�÷ӧҹ��������� 232% ��� 238% ��袹Ҵ���ҹء�� �ӹǹ
3,963 �� ��� 17859 �� ����ӴѺ
�͡��â�Ҵ 7,686 �ѡ��..�ç���ҧ������Ẻ���........����
���ҹء����Ҵ 3,963 ��............19 �Թҷ�......1.59 �Թҷ�
���ҹء����Ҵ 17,859 ��...........90 �Թҷ�.....2.36 �Թҷ�
�͡��â�Ҵ 25,846 �ѡ��..�ç���ҧ������Ẻ���.......����
���ҹء����Ҵ 3,963 ��............63 �Թҷ�.....5.00 �Թҷ�
���ҹء����Ҵ 17,859 ��..........304 �Թҷ�.....5.59 �Թҷ�
��ػ
�ҡ��÷��ͧ���ç���ҧ������Ẻ���¹�����ҧ���ҹء�����͡�õѴ��������
���������ö�ӧҹ���Ǵ���ǡ����ç���ҧ������Ẻ�������ԧ����ʵ�Ẻ���§�ӴѺ���ѹ
�ҡ �·���������㹡�÷ӧҹ����ҧ�Ф����֧����͡��è��բ�Ҵ��ҧ�ѹ ���Ͷ֧�������
�ӹǹ��㹾��ҹء������ա�繨ӹǹ�ҡ ��������㹡�÷ӧҹ���ѧ��������� 㹢�з��
�ç���ҧ������Ẻ������դ�������㹡�÷ӧҹ����üѹ�Ѻ�ӹǹ��㹾��ҹء�����
��Ҵ�ͧ�͡������ѹ�ҡ��駹�����ͧ�ҡ�������Ǣͧ��÷ӧҹ�ͧ�ç���ҧ������Ẻ�
��¨Т������Ѻ������Ǣͧ��㹾��ҹء�����üѹ�Ѻ�ӹǹ����Т�Ҵ�����Ź����ҡ
�͡�����ҧ�ԧ
[1] Witoon Kanlayanawat, Somchai Prasitjutrakul, "Autometic Indexing for Thai Text
with Unknown Words using Trie Structure" ,
Dept. of Computer Engineering, Chulalongkorn University, NCSEC98 conference,
Kasetsart University, 1998
[2] Mark Allen Weiss, "Data Structures and Algorithm Analysis in C", Florida
International University,
The Benjamin/Cummings Publishing Co., ltd., 1992