Arabic string searching in the context of character code standards and orthographic variations

摘要

In this paper, the problems of searching in Arabic text for finding a given pattern is considered from a practical perspective. Orthographic and character encoding variations are discussed. Four of the well known string searching algorithms have been modified to handle Arabic text and their performance has been examined and analyzed using vocalized and unvocalized Arabic texts of varying length. All algorithms could be modified to support the handling of diacritics, but only three could support spelling variant checking. The empirical results show that the Boyer--Moore--Horspool algorithm provides the best overall running time performance in dealing with Arabic text in terms of both the average number of comparisons and the average actual machine execution time. Most of the increase rate in the complexity of BMH is attributed to spelling variant checking, in comparison with the efficiency of handling diacritics.