On Tag Insertion and it's Complexity.
Stuart Yeates, Ian H. Witten · 2000
Many text mining problems can be recast as tag insertion problems---we illustrate several. The size of the search space of the tag insertion problem is explored, using a number of proofs and heuristics (Viterbi Search, One-Tag-at-a-Time and Automatic Tokenisation) to greatly reduce the size of the search space, reducing the size of the search space from approximately 10 400 to approximately 10 11 . Properties of the SGML standard are also used to reduce the complexity of the search. A number of examples taken from bibliographies are worked through, showing search space size, possible errors and examples of recall and precision rates. 1 Introduction Many text mining operations can be recast as tag insertion problems. A simple example is the word segmentation problem: to locate word boundaries in natural language text in which all the words are run together [17]. Western languages such as English are always written with explicit spaces between the words, the only ambiguities being ...