A breadth-first representation for tree matching in large scale forest-based translation

Sumukh Ghodke; Steven Bird; Rui Zhang

A breadth-first representation for tree matching in large scale forest-based translation

Sumukh Ghodke, Steven Bird, Rui Zhang

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings › peer-review

Abstract

Efficient data structures are necessary for searching large translation rule dictionaries in forest-based machine translation. We propose a breadth-first representation of tree structures that allows trees to be stored and accessed efficiently. We describe an algorithm that allows incremental search for trees in a forest and show that its performance is orders of magnitude faster than iterative search. A B-tree index is used to store the rule dictionaries. Prefix-compressed indexes with a large page size are found to provide a balance of fast search and disk space utilisation.

Original language	English
Title of host publication	Proceedings of 5th International Joint Conference on Natural Language Processing
Pages	785-793
Number of pages	9
Publication status	Published - 2011
Externally published	Yes
Event	International Joint Conference on Natural Language Processing - Chiang Mai, Thailand Duration: 8 Nov 2011 → 13 Nov 2011 Conference number: 5th

Conference

Conference	International Joint Conference on Natural Language Processing
Country/Territory	Thailand
City	Chiang Mai
Period	8/11/11 → 13/11/11

Access to Document

https://www.aclweb.org/anthology/I11-1088Licence: CC BY

Cite this

@inproceedings{2439e708f08648178723c3230bd1eb10,

title = "A breadth-first representation for tree matching in large scale forest-based translation",

abstract = "Efficient data structures are necessary for searching large translation rule dictionaries in forest-based machine translation. We propose a breadth-first representation of tree structures that allows trees to be stored and accessed efficiently. We describe an algorithm that allows incremental search for trees in a forest and show that its performance is orders of magnitude faster than iterative search. A B-tree index is used to store the rule dictionaries. Prefix-compressed indexes with a large page size are found to provide a balance of fast search and disk space utilisation.",

author = "Sumukh Ghodke and Steven Bird and Rui Zhang",

year = "2011",

language = "English",

pages = "785--793",

booktitle = "Proceedings of 5th International Joint Conference on Natural Language Processing",

note = "International Joint Conference on Natural Language Processing ; Conference date: 08-11-2011 Through 13-11-2011",

}

TY - GEN

T1 - A breadth-first representation for tree matching in large scale forest-based translation

AU - Ghodke, Sumukh

AU - Bird, Steven

AU - Zhang, Rui

N1 - Conference code: 5th

PY - 2011

Y1 - 2011

N2 - Efficient data structures are necessary for searching large translation rule dictionaries in forest-based machine translation. We propose a breadth-first representation of tree structures that allows trees to be stored and accessed efficiently. We describe an algorithm that allows incremental search for trees in a forest and show that its performance is orders of magnitude faster than iterative search. A B-tree index is used to store the rule dictionaries. Prefix-compressed indexes with a large page size are found to provide a balance of fast search and disk space utilisation.

AB - Efficient data structures are necessary for searching large translation rule dictionaries in forest-based machine translation. We propose a breadth-first representation of tree structures that allows trees to be stored and accessed efficiently. We describe an algorithm that allows incremental search for trees in a forest and show that its performance is orders of magnitude faster than iterative search. A B-tree index is used to store the rule dictionaries. Prefix-compressed indexes with a large page size are found to provide a balance of fast search and disk space utilisation.

M3 - Conference Paper published in Proceedings

SP - 785

EP - 793

BT - Proceedings of 5th International Joint Conference on Natural Language Processing

T2 - International Joint Conference on Natural Language Processing

Y2 - 8 November 2011 through 13 November 2011

ER -

A breadth-first representation for tree matching in large scale forest-based translation

Abstract

Conference

Access to Document

Fingerprint

Cite this