{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T01:32:50Z","timestamp":1760059970503,"version":"build-2065373602"},"reference-count":18,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2025,7,22]],"date-time":"2025-07-22T00:00:00Z","timestamp":1753142400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Axioms"],"abstract":"<jats:p>Let \u03a3 be a nonempty set of characters, called an alphabet. The run-length encoding (RLE) algorithm processes any nonempty string u over \u03a3 and produces two outputs: a k-tuple (b1,b2,\u2026,bk), where each bi is a character and bi+1\u2260bi; and a corresponding k-tuple (q1,q2,\u2026,qk) of positive integers, so that the original string can be reconstructed as u=b1q1b2q2\u2026bkqk. The integer k is termed the run-length of u, and symbolized by \u03c1(u). By convention, we let \u03c1(\u03b5)=0. In the Euclidean space (Rn,\u2225\u00b7\u22252), the volume of a sphere is determined solely by the dimension n and the radius, following well-established formulas. However, for spheres of strings under the edit metric, the situation is more complex, and no general formulas have been identified. This work intended to show that the volume of the sphere SL(u,1), composed of all strings of Levenshtein distance 1 from u, is dependent on the specific structure of the \u201cRLE-decomposition\u201d of u. Notably, this volume equals (2l(u)+1)s\u22122l(u)\u2212\u03c1(u), where \u03c1(u) represents the run-length of u and l(u) denotes its length (i.e., the number of characters in u). Given an integer p\u22652, we present a partial result concerning the computation of the volume |SL(u,p)| in the specific case where the run-length \u03c1(u)=1. More precisely, for a fixed integer n\u22651 and a character a\u2208\u03a3, we explicitly compute the volume of the Levenshtein sphere of radius p, centered at the string u=an. This case corresponds to the simplest run structure and serves as a foundational step toward understanding the general behavior of Levenshtein spheres.<\/jats:p>","DOI":"10.3390\/axioms14080550","type":"journal-article","created":{"date-parts":[[2025,7,22]],"date-time":"2025-07-22T13:35:28Z","timestamp":1753191328000},"page":"550","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Spheres of Strings Under the Levenshtein Distance"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-2197-9122","authenticated-orcid":false,"given":"Said","family":"Algarni","sequence":"first","affiliation":[{"name":"Department of Mathematics, College of Computing and Mathematics, King Fahd University of Petroleum and Minerals, Dhahran 31261, Saudi Arabia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0082-7644","authenticated-orcid":false,"given":"Othman","family":"Echi","sequence":"additional","affiliation":[{"name":"Department of Mathematics, College of Computing and Mathematics, King Fahd University of Petroleum and Minerals, Dhahran 31261, Saudi Arabia"}]}],"member":"1968","published-online":{"date-parts":[[2025,7,22]]},"reference":[{"key":"ref_1","first-page":"707","article-title":"Binary codes capable of correcting deletions, insertions, and reversals","volume":"10","author":"Levenshtein","year":"1966","journal-title":"Sov. Phys. Dokl."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/s10579-009-9114-z","article-title":"Cross-language plagiarism detection","volume":"45","author":"Stein","year":"2011","journal-title":"Lang Resour. Eval."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Brill, E., and Moore, R.C. (2000, January 3\u20136). An improved error model for noisy channel spelling correction. Proceedings of the 38th Annual Meeting on Association for Computational Linguistics, Hong Kong, China.","DOI":"10.3115\/1075218.1075255"},{"key":"ref_4","unstructured":"Koehn, P. (2005, January 12\u201316). Europarl: A Parallel Corpus for Statistical Machine Translation. Proceedings of the 10th Machine Translation Summit, Phuket, Thailand."},{"key":"ref_5","unstructured":"Jurafsky, D., and Martin, J.H. (2008). Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition, Prentice Hall."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1002\/j.1538-7305.1950.tb00463.x","article-title":"Error detecting and error correcting codes","volume":"29","author":"Hamming","year":"1950","journal-title":"Bell Syst. Tech. J."},{"key":"ref_7","unstructured":"Katz, J., and Lindell, Y. (2021). Introduction to Modern Cryptography, CRC Press. [3rd ed.]. Chapman & Hall\/CRC Cryptography and Network Security."},{"key":"ref_8","unstructured":"Lin, S., and Costello, D.J. (2004). Error Control Coding: Fundamentals and Applications, Pearson\/Prentice Hall. [2nd ed.]."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1145\/1327452.1327494","article-title":"Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions","volume":"51","author":"Andoni","year":"2018","journal-title":"Commun. ACM"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.tcs.2017.10.026","article-title":"Period recovery of strings over the Hamming and edit distances","volume":"710","author":"Amir","year":"2018","journal-title":"Theor. Comput. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"i127","DOI":"10.1093\/bioinformatics\/btz354","article-title":"Locality-sensitive hashing for the edit distance","volume":"35","author":"DeBlasio","year":"2019","journal-title":"Bioinformatics"},{"key":"ref_12","first-page":"260","article-title":"On the encoding of arbitrary geometric configurations","volume":"10","author":"Malon","year":"1961","journal-title":"IRE Trans. EC"},{"key":"ref_13","first-page":"128202","article-title":"Volume formula and growth rates of the balls of strings under the edit distances","volume":"458","author":"Koyano","year":"2023","journal-title":"Appl. Math. Comput."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1016\/j.dam.2021.01.028","article-title":"Connectivity and diagnosability of center k-ary n-cubes","volume":"294","author":"Wang","year":"2021","journal-title":"Discrete Appl. Math."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1051\/ita\/2017008","article-title":"The connectivity and nature diagnosability of expanded k-ary n-cubes","volume":"51","author":"Wang","year":"2017","journal-title":"RAIRO Theor. Inform. Appl."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1051\/ita\/2014022","article-title":"On minimal Hamming compatible distances","volume":"48","author":"Bakhtary","year":"2014","journal-title":"RAIRO Theor. Inform. Appl."},{"key":"ref_17","unstructured":"de Moivre, A. (1967). The Doctrine of Chances: Or, a Method of Calculating the Probabilities of Events in Play, Chelsea Publishing Company."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/375360.375365","article-title":"A guided tour to approximate string matching","volume":"33","author":"Navarro","year":"2001","journal-title":"ACM Comput. Surv."}],"container-title":["Axioms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2075-1680\/14\/8\/550\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T18:14:03Z","timestamp":1760033643000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2075-1680\/14\/8\/550"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,22]]},"references-count":18,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2025,8]]}},"alternative-id":["axioms14080550"],"URL":"https:\/\/doi.org\/10.3390\/axioms14080550","relation":{},"ISSN":["2075-1680"],"issn-type":[{"type":"electronic","value":"2075-1680"}],"subject":[],"published":{"date-parts":[[2025,7,22]]}}}