检索结果-内蒙古大学图书馆

Automatic performance evaluation of printed Chinese character recognition systems

International Journal on Document Analysis and Recognition 2002年第3期4卷 177-182页

作者： Fang, Chi Liu, Changsong Peng, Liangrui Ding, Xiaoqing State Key Laboratory of Intelligent Technology and Systems Department of Electronic Engineering Tsinghua University Beijing 100084 China

Performance evaluation is crucial for improving the performance of OCR systems. However, this is trivial and sophisticated work to do by hand. Therefore, we have developed an automatic performance evaluation system for a printed Chinese character recognition (PCCR) system. Our system is characterized by using real-world data as test data and automatically obtaining the performance of the PCCR system by comparing the correct text and the recognition result of the document image. In addition, our performance evaluation system also provides some evaluation of performance for the segmentation module, the classification module, and the post-processing module of the PCCR system. For this purpose, a segmentation error-tolerant character-string matching algorithm is proposed to obtain the correspondence between the correct text and the recognition result. The experiments show that our performance evaluation system is an accurate and powerful tool for studying deficiencies in the PCCR system. Although our approach is aimed at the PCCR system, the idea also can be applied to other OCR systems. © 2002 Springer-Verlag Berlin Heidelberg.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

On maximal suffices and constant-space linear-time versions of KMP algorithm 5

引用

5th Latin American Symposium on Theoretical Informatics (LATIN 2002)

作者： Rytter, W Univ Liverpool Dept Comp Sci Liverpool L69 7ZF Merseyside England

ISBN: (纸本)3540434003

We investigate several simple ways of transforming Knuth-Morris-Pratt algorithm (KMP) into a constant-space and still linear time string-matching algorithm. We also identify a class of very special patterns for which the transformation is particularly simple and show usefulness of the class. Constant-space linear-time string-matching algorithms are usually very sophisticated. Most of them consist of two phases: (very technical) preprocessing phase and searching phase. An exception is one-phase Crochemore's algorithm [2]. It is an on-line version of KMP algorithm with "on-the-fly" computation of pattern shifts (as approximate periods). We explore further Crochemore's approach, and construct alternative algorithms which are differently structured. In Crochemore's algorithm the approximate-period function is restarted from inside, which means that several internal variables of this function are changing globally, also Crochemore's algorithm strongly depends on the concrete implementation of approximate-periods computation. We present a simple modification of KMP algorithm which works in O(1)-space, O(n)-time for any function which computes periods or approximate periods in O(1)-space, and linear time. The approximate-period function can be treated as a black box. We show also that lexicographically self-maximal patterns are especially well suited for Crochemore-style string matching. A new O(1)-space string-matching algorithm, MaxSuffix-Matching, is proposed in the paper, which gives yet another example of applicability of maximal suffices.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

Pattern matching over multi-attribute data streams 9th

引用

9th International Symposium on string Processing and Information Retrieval, SPIRE 2002

作者： Harada, Lilian Fujitsu Laboratories Ltd 4-1-1 Kamikodanaka Nakahara-ku KawasakiKanagawa211-8588 Japan

ISBN: (纸本)3540441581

Recently a growing number of applications monitor the physical world by detecting some patterns and trends of interest. In this paper we present two algorithms that generalize string-matching algorithms for detecting patterns with complex predicates over data streams having multiple categorical and quantitative attributes. Implementation and evaluation of the algorithms show their efficiency when compared to the naive approach. © Springer-Verlag Berlin Heidelberg 2002.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient experimental string matching by weak factor recognition 1

引用

12th Annual Symposium on Combinatorial Pattern Matching, CPM 2001

作者： Allauzen, Cyril Crochemore, Maxime Raffinot, Mathieu Institut Gaspard-Monge Université de Marne-la-Vallée Cité Descartes Champs-sur-Marne Marne-la-Vallée Cedex 277454 France Equipe génome cellule et informatique Université de Versailles 45 avenue des Etats-Unis Versailles Cedex78035 France

ISBN: (数字)9783540481942

ISBN: (纸本)3540422714

We introduce a new notion of weak factor recognition that is the foundation of new data structures and on-line string matching algorithms. We define a new automaton built on a string p = p1p2… pm that acts like an oracle on the set of factors pi…pj. If a string is recognized by this automaton, it may be a factor of p. But, if it is rejected, it is surely not a factor. We call it factor oracle. More precisely, this automaton is acyclic, recognizes at least the factors of p, has m+ 1 states and a linear number of transitions. We give a very simple sequential construction algorithm to build it. Using this automaton, we design an efficient experimental on-line string matching algorithm (we conjecture its optimality in regard to the experimental results) that is really simple to implement. We also extend the factor oracle to predict that a string could be a suffix (i.e. in the set pi… pm) of p. We obtain the suffix oracle, that enables in some cases a tricky improvement of the previous string matching algorithm. © Springer-Verlag Berlin Heidelberg 2001.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

Simple optimal string matching algorithm

Simple optimal string matching algorithm

引用

11th Annual Symposium on Combinatorial Pattern Matching (CPM 2000)

作者： Allauzen, C Raffinot, M Univ Marne La Vallee Inst Gaspard Monge F-77454 Marne La Vallee 2 France

ISBN: (纸本)3540676333

We present a new string matching algorithm linear in the worst case (in O(m + n) where n is the size of the text and m the size of the searched word, both taken on an alphabet Sigma) and optimal on average (with equiprobability and independence of letters, in O(m + n log\Sigma\ m/m)). Of all the algorithms that verify these two complexities, our is the simplest since it uses only a single structure, a suffix automaton. Moreover, its preprocessing phase is linearly dynamical, i,e. it is possible to search the words p(i), then p(1)p(2),p(1)p(2)p(3), p(1)p(2)p(3)... p(i) with O(Sigma \pi\) total preprocessing time. Among the algorithms that verify this property (for instance the Knuth-Morris-Pratt) our algorithm is the only one to be optimal on average.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

Korean folk song retrieval using rhythm pattern classification

Korean folk song retrieval using rhythm pattern classificati...

引用

5th International Symposium on Signal Processing and Its Applications, ISSPA 1999

作者： Yang, Chul Yong Shin, Jong Tak Kim, Jin Wook Kim, Hang Joon Artificial Lab. Dept. of Computer Engineering Kyungpook National University 1370 Sankyuk-dong Pook-gu Taegu Korea Republic of

ISBN: (纸本)1864354518

In content based music retrieval, approximate string matching approaches are frequently used. Though string matching algorithms effectively deal with the input fault tolerance of user query, they require much time to search the entire database. In this paper, we propose a Korean folk song retrieval method which efficiently search the database. A user query is searched in two steps, a coarse classification using rhythm pattern and an interval comparison based on approximate string matching. The experimental results show that the proposed method efficiently improve the retrieval time. © 1999 IEEE.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

A very fast string matching algorithm for small alphabets and long patterns

A very fast string matching algorithm for small alphabets an...

引用

9th Annual Symposium on Combinatorial Pattern Matching, CPM 1998

作者： Charras, Christian Lecro, Thierry Pehoushek, Joseph Daniel LIR Faculté des Sciences et des Techniques Universit é de Rouen 76128 Mont Saint-Aignan cedex France

ISBN: (纸本)3540647392

We are interested in the exact string matching problem which consists of searching for all the occurrences of a pattern of length m in a text of length n. Both the pattern and the text are built over an alphabet • of size a. %Ve present three versions of an exact string matching algorithm. They use a new shifting technique. The first version is straightforward and easy to implement. The second version is linear in the worst case, an improvement over the first. The main result is the third algorithm. It is very fast in practice for small alphabet and long patterns. Asymptotically, it performs O(log m(m + n/(m- log m))) inspections of text symbols in the average case. This compares favorably with many other string searching algorithms.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

Enhancing partial deduction via unfold/fold rules 6th

引用

6th International Workshop on Logic Program Synthesis and Transformation (LOPSTR 96) / 6th Inductive Logic Programming Workshop (ILP 96)

作者： Pettorossi, A Proietti, M Renault, S CNR IST ANAL SISTEMI & INFORMAT I-00185 ROME ITALY

ISBN: (纸本)3540627189

We show that sometimes partial deduction produces poor program specializations because of its limited ability in (i) dealing with conjunctions of recursively defined predicates, (ii) combining partial evaluations of alternative computations, and (iii) taking into account unification failures. We propose to extend the standard partial deduction technique by using versions of the definition rule and the folding rule which allow us to specialize predicates defined by disjunctions of conjunctions of goals. We also consider a case split rule to take into account unification failures. Moreover, in order to perform program specialization via partial deduction in an automatic way, we propose a transformation strategy which takes as parameters suitable substrategies for directing the application of every transformation rule. Finally, we show through two examples that our partial deduction technique is superior to standard partial deduction, The first example refers to the automatic derivation of the Knuth-Morris-Pratt string matching algorithm, and the second example refers to the construction of a parser for a given regular expression. In both examples, the specialized programs are derived starting from naive, non-deterministic initial programs, whereas standard partial deduction can derive similar specialized programs only when complex, deterministic initial programs are provided.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

A type generator model for adaptive lossy compression

A type generator model for adaptive lossy compression

引用

1997 IEEE International Symposium on Information Theory, ISIT 1997

作者： Zamir, Ram Rose, Kenneth Dept. of EE - Systems Tel Aviv University Tel Aviv 69978 Israel Dept. of ECE University of California Santa Barbara CA 93106 United States

ISBN: (纸本)0780339568

We propose a random coding model which gives insight into the underlying mechanism of lossy string-matching algorithms. This idealised model is based on manipulating types rather than codewords. We model the adaptive codebook as a mixed type random code, whose type distribution evolves with time as its dimension increases. The model behavior exhibits a mechanism of natural type selection which reinforces «good types». © 1997 IEEE.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

Gaining efficiency on the word-length string searching algorithm

引用

Calcolo 1997年第1-4期34卷 102-124页

作者： Mhashi, Mahmoud M. Computer Science Department Mu'tah University P.O. Box 7 Mu'tah Al-Karak Jordan

The word-length string searching algorithm searches for all occurrences of a specified string, the pattern, in another string, the text. This is done by comparing the word-length in the pattern with the corresponding word-length in the text. If there is an exact length match, the searching process goes to the character level. The word-length algorithm was already presented in [6] and compared with straight forward algorithm and Raita's Algorithm. This paper presents a new implementation of word-length algorithm which takes the advantage of the depedencies between the word-lengths in the pattern. Three string searching algorithms: wordlength (WL), WL with next table (WLN), and WLN with the a-match technique (WLNA) are studied and investigated for the average number of comparisons per number/character passed using two different types of texts: natural language and random. Empirical results revealed that on the average, the WLN algorithm reduces 10.3% and 13.2% of the number of comparisons required by the WL algorithm to find all the occurrences of the pattern in the natural language text and the random text respectively. Unfortunately, for the WLNA algorithm there was no significant reduction at all.

关键词： string searching algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：