Thumbnail
Access Restriction
Subscribed

Author Reams, Charles
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2012
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Constraint satisfaction ♦ Binary decision diagram ♦ Heuristics ♦ Natural language
Abstract Natural language is a rich source of constraint satisfaction problems (CSPs), with a uniquely structured solution domain. We describe a number of approaches to satisfying the particular case of unordered letter-level constraints, including anagrams, but also relevant to typographical error correction, password security and word puzzles among other fields. We define the $\textit{anatree},$ a data structure that can solve many such problems in constant time with respect to the size of the lexicon. The structure represents the lexicon of a language in a format somewhat analogous to a binary decision diagram (BDD) and, as with BDDs, construction heuristics allow the real average-case performance to vastly exceed the theoretical worst case. We compare anatrees and their alternatives empirically, explore the behavior of the construction heuristics, and characterize the tasks for which each is best suited.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2012-03-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 17
Page Count 16
Starting Page 1.1
Ending Page 1.16


Open content in new tab

   Open content in new tab
Source: ACM Digital Library