Elamur Research⌕
☰
home / papers / 2013 / A Hybrid Algorithm for Matching Arabic Names

A Hybrid Algorithm for Matching Arabic Names

Paper · 2013 · T.El-Shishtawy

Summary

Linking records about the same person across databases depends on reliable name matching. Arabic names make this hard for three reasons: different names often have very similar spellings, components follow a fixed order, and people often drop middle or common parts of their name. Character-level metrics handle typos but miss dropped tokens. Bag-of-words token metrics handle dropped tokens but ignore order and small misspellings.

El-Shishtawy proposes a hybrid that applies Levenshtein edit distance to whole name tokens instead of characters. The two names are aligned in sequence. Each token insertion, deletion or substitution gets a cost that depends on the token's position in the name, its frequency in an Arabic name frequency table, and its character-level similarity to the other token. A threshold decides when two tokens count as equal.

The method was tested on a large Arabic dataset with controlled distortions and compared with Levenshtein, Monge-Elkan, Jaro-Winkler and Soft-TFIDF. A match counted as a success only if the correct name was ranked first. The hybrid had the narrowest spread between its worst and best results, so it should be more robust when the mix of real-world errors is unknown.

Key points

  • The baselines came from the open-source Java SecondString toolkit: basic Levenshtein, Monge-Elkan, Jaro-Winkler and Soft-TFIDF (run on top of JW).
  • The reported setting used a position weight β=0.7 together with a character-similarity threshold.
  • Character errors:
    • Plain Levenshtein reached 100% on one- and two-character errors.
    • The hybrid scored 95.7% and 90.7%, roughly level with Soft-TFIDF.
    • Monge-Elkan scored lowest, at 66.7% and 44.3%.
  • Token omissions:
    • The hybrid's success ranged from 80.3% to 99.7%.
    • Soft-TFIDF ranged from 69.0% to 94.3%.
    • Plain Levenshtein fell to 16% when the second and third tokens were both dropped.
  • The author claims the approach transfers to other languages with ordered names, frequent omission of middle components and few abbreviations. Only the name frequency table would need replacing. Cross-language matching is listed as future work.

Interesting ideas

  • I1. Running edit distance over whole tokens keeps word order, and weighting each operation by position, frequency and spelling similarity makes dropping a rare first token cost more than dropping a common middle one.
  • I2. A single character-similarity threshold acts as a dial between two behaviours: at one extreme the metric works purely on tokens and ignores misspellings, at the other it behaves like a character-level metric.
  • I3. Instead of one average, each method is scored per error type and judged by the span between its worst and best case, with a narrow span read as robustness.
  • I4. Test sets are built by deliberately corrupting clean names in controlled ways (one or two character errors, dropping the first, second or third token) to isolate each failure mode.
  • I5. Success is counted only when the correct answer is the top-scored candidate, because the goal is a fully automatic pipeline.

For Mova

How these ideas could serve Mova, our small open language model — its files, stages and tests:

  • I1 (frames): coreference between named mentions ("Dr. Anna Maria Kovac" vs "Anna Kovac") could use such an order-aware, frequency-weighted token alignment instead of string overlap, and the alignment itself is explainable.
  • I2 (world): when linking text entities to Wikidata or the knowledge graph, one tunable threshold could switch between strict and spelling-tolerant matching depending on how noisy the source text is.
  • I3 (learn): evaluation reports could list results per perturbation family (typos, dropped words, reordering) and track the worst case, so that one strong category cannot hide a weak one.
  • I4 (tree): applying controlled corruptions such as typos or deleted modifiers to treebank sentences would show which kinds of noise break the parser most.
  • I5 (answer): QA and school-test readers should be scored on top-1 correctness rather than on whether the right answer appears somewhere in a ranked list.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Fields, topics and concepts

📚 Shelves 6The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 worksDecision Sciences · 249 worksManagement Science and Operations Research · 134 works

🧭 Topics 1Research subjects and languages the work is about.Semitic languages · 3,066 works

Cite

Cite as T.El-Shishtawy. 2013. A Hybrid Algorithm for Matching Arabic Names. arXiv:1309.5657 · International Journal of Computational Linguistics Research Volume 4 Number 2 June 2013.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1309.5657 · arXiv 1309.5657

@misc{telshishtawy2013hybrid,
  title = {{A Hybrid Algorithm for Matching Arabic Names}},
  author = {T.El-Shishtawy},
  year = {2013},
  doi = {10.48550/arxiv.1309.5657},
  eprint = {1309.5657},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1309.5657}
}

References

22 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Bilenko, M., Mooney, R., Cohen, W., Ravikumar, P., & Fienberg, S. (2003). Adaptive name matching in information integration. Intelligent Systems, IEEE, 18(5), 16-23. ↗
  2. Bilenko, M., & Mooney, R. J. (2003, August). Adaptive duplicate detection using learnable string similarity measures. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 39-48). ACM. find
  3. Bilenko, M., Mooney, R., Cohen, W., Ravikumar, P., & Fienberg, S. (2003). Adaptive name matching in information integration. Intelligent Systems, IEEE, 18(5), 16-23. ↗
  4. Borgman, C. L., & Siegfried, S. L. (1999). Getty's Synoname™ and its cousins: A survey of applications of personal name‐matching algorithms. Journal of the American Society for Information Science, 43(7), 459-476 find
  5. Camacho, D., Huerta, R., & Elkan, C.(2008) An Evolutionary Hybrid Distance for Duplicate String Matching. http://arantxa.ii.uam.es/~dcamacho/ StringDistance/ hybrid-distance.pdf . ↗
  6. Cohen, W. W., Ravikumar, P., & Fienberg, S. E. (2003, August). A comparison of string distance metrics for name-matching tasks. In Proceedings of the IJCAI-2003 Workshop on Information Integration on the Web (IIWeb-03) (pp. 73-78). find
  7. Elmagarmid, A. K., Ipeirotis, P. G., & Verykios, V. S. (2007). Duplicate record detection: A survey. Knowledge and Data Engineering, IEEE Transactions on, 19(1), 1-16. ↗
  8. Gadd, T. N. (1990). PHONIX: The algorithm. Program: electronic library and information systems, 24(4), 363-366. ↗
  9. Hall, P. A., & Dowling, G. R. (1980). Approximate string matching. ACM Computing Surveys (CSUR), 12(4), 381-402. ↗
  10. Holmes, D., & McCabe, M. C. (2002, April). Improving precision and recall for soundex retrieval. In Information Technology: Coding and Computing, 2002. Proceedings. International Conference on (pp. 22-26). IEEE. find
  11. Jaro, M. A. (1989). Advances in record-linkage methodology as applied to matching the 1985 census of Tampa, Florida. Journal of the American Statistical Association, 84(406), 414-420. ↗
  12. Jurafsky, D., Martin, J. H., & Kehler, A. (2002). Speech and language processing: an introduction to natural language processing, computational linguistics and speech recognition (Vol. 2). Prentice Hall. find
  13. Keskustalo, H., Pirkola, A., Visala, K., Leppänen, E., & Järvelin, K. (2003). Non-adjacent digrams improve matching of cross-lingual spelling variants. In String Processing and Information Retrieval (pp. 252-265). Springer Berlin/Heidelberg. find
  14. Monge, A. E., & Elkan, C. (1996, August). The field matching problem: Algorithms and applications. In Proceedings of the second international Conference on Knowledge Discovery and Data Mining (pp. 267-270). find
  15. Moreau, E., Yvon, F., & Cappé, O. (2008, August). Robust similarity measures for named entities matching. In Proceedings of the 22nd International Conference on Computational Linguistics-Volume 1 (pp. 593-600). Association for Computational Linguistics. find
  16. Patman, F., & Thompson, P. (2003). Names: A new frontier in text mining. Intelligence and Security Informatics, 960-960. find
  17. Smith, T. F., & Waterman, M. S. (1981). ªIdentification of Common Molecular Subsequences, º J. Molecular Biology, 147, 195-197. find
  18. Snae, C. (2007). A comparison and analysis of name matching algorithms. International Journal of Applied Science. Engineering and Technology, 4(1), 252-257. ↗
  19. Waterman, M. S., Smith, T. F., & Beyer, W. A. (1976). Some biological sequence metrics. Advances in Mathematics, 20(3), 367-387. ↗
  20. Winkler, W. E. (2002). Methods for record linkage and Bayesian networks. Technical report, Statistical Research Division, US Census Bureau, Washington, DC. find
  21. Winkler, W. E. (2006). Overview of record linkage and current research directions. In Bureau of the Census. find
  22. Xiao, C., Wang, W., Lin, X., Yu, J. X., & Wang, G. (2011). Efficient similarity joins for near-duplicate detection. ACM Transactions on Database Systems (TODS), 36(3), 15. ↗

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/t-el-shishtawy-2013-hybrid-algorithm-matching-arabic-names/