Finite-state script normalization and processing utilities: The N isaba B rahmic library (2021)

Abstract: This paper presents an open-source library for efficient low-level processing of ten major South Asian Brahmic scripts. The library provides a flexible and extensible framework for supporting crucial operations on Brahmic scripts, such as NFC, visual normalization, reversible transliteration, and validity checks, implemented in Python within a finite-state transducer formalism. We survey some common Brahmic script issues that may adversely affect the performance of downstream NLP tasks, and provide the rationale for finite-state design and system implementation details.

## introduction the unicode standard separates the representation of text from its specific graphical rendering: text is encoded as a sequence of characters, which, at presentation time are then collectively rendered into the appropriate sequence of glyphs for display. this can occasionally result in manytoone map pings, where several distinctlyencoded strings can result in identical display. for example, latin script letters with diacritics such as "é" can gener ally be encoded as either: (a) a pair of the base let ter (e.g., "e" which is u+0065 from unicode's ba sic latin block, corresponding to ascii) and a dia critic (in this case u+0301 from the combining dia critical marks block); or (b) a single character that represents the grapheme directly (u+00e9 from the latin1 supplement unicode block). both encod ings yield visually identical text, hence text is of ten normalized to a conventionalized normal form, such as the wellknown normalization form c (nfc), so that visually identical words are mapped to a conventionalized representative of their equiv alence class for downstream processing. critically, nfc normalization falls far short of a complete handling of such manytoone phenomena in uni code. in addition to such normalization issues, some scripts also have wellformedness constraints, i.e., not all strings of unicode characters from a single script correspond to a valid (i.e., legible) grapheme sequence in the script. such constraints do not ap ply in the basic latin alphabet, where any permuta tion of letters can be rendered as a valid string (e.g., for use as an acronym). the brahmic family of scripts, however, including the devanagari script used to write hindi, marathi and many other south asian languages, do have such constraints. these scripts are alphasyllabaries, meaning that they are structured around orthographic syllables (aks ̣ara) as the basic unit. 1 one or more unicode characters combine when rendering one of thousands of leg ible aks ̣ara, but many combinations do not corre spond to any aks ̣ara. given a token in these scripts, one may want to (a) normalize it to a canonical form; and (b) check whether it is a wellformed sequence of aks ̣ara. brahmic scripts are heavily used across south asia and have official status in india, bangladesh, nepal, sri lanka and beyond @xcite . despite evident progress in localization standards (unicode @xcite and improvements in associated technolo gies such as input methods @xcite and character recognition @xcite , brahmic script processing still poses important challenges due to the inherent differences between these writ ing systems and those which historically have been more dominant in information technology @xcite . in this paper, we present nisaba, an opensource software library, 2 which provides processing utili ties for ten major brahmic scripts of south asia: bengali, devanagari, gujarati, gurmukhi, kan nada, malayalam, oriya (odia), sinhala, tamil, and telugu. in addition to string normaliza tion and wellformedness processing, the library also includes utilities for the deterministic and re versible romanization of these scripts, i.e., translit eration from each script to and from the latin script @xcite . while the resulting roman izations are standardized in a way that may or may not correspond to how native speakers tend to ro manize the text in informal communication (see, e.g., @xcite , such a default romaniza tion can permit easy inspection of an approximate version of the linguistic strings for those who read the latin script but not the specific brahmic script being examined. as a whole, the library provides important utili ties for language processing applications of south asian languages using brahmic scripts. the de sign is based on the observation that, while there are considerable superficial differences between these scripts, they follow the same encoding model in unicode, and maintain a very similar char acter repertoire having evolved from the same source -the brāhmī script @xcite . this observation lends itself to the scriptagnostic design (outlined in §4) that, unlike other approaches reviewed in §2, is based on the weighted finite state transducer (wfst) formal ism @xcite . the details of our system are provided in §5. ## related work the computational processing of brahmic scripts is not a new topic, with the first applications dating back to the early formal syntactic work by @xcite . with an increased focus on the south asian languages within the nlp commu nity, facilitated by advances in machine learning and the increased availability of relevant corpora, multiple script processing solutions have emerged. some of these toolkits, such as statistical ma chine translationbased brahminet @xcite , are modelbased, while oth ers, such as uroman @xcite , indicnlp @xcite , and akshar mukha (rajan, 2020), employ rules. the main fo cus of these libraries is script conversion and ro manization. in this capacity they were success fully employed in diverse downstream multilin gual nlp tasks such as neural machine transla tion @xcite , morphological analysis @xcite , named entity recogni tion @xcite and partofspeech tag ging @xcite . similar to the software mentioned above, our li brary does provide romanization, but unlike some of the packages, such as uroman, we guarantee reversibility from latin back to the native script. similar to others we do not focus on faithful in vertible transliteration of named entities which typically requires modelbased approaches @xcite . unlike the indicnlp pack age, our software does not provide morphologi cal analysis, but instead offers significantly richer script normalization capabilities than other pack ages. these capabilities are functionally sepa rated into normalization to normalization form c (nfc) and visual normalization. additionally, our library provides extensive scriptspecific well formedness grammars. finally, in contrast to these other approaches, grammars in our library are maintained separately from the code for compila tion and application, allowing for maintenance of existing scripts and languages plus extension to new ones without having to modify any code. this is particularly important given that unicode stan dards do change over time and there remain many languages left to cover. to the best of our knowledge this is the first publicly available general finitestate grammar ap proach for lowlevel processing of multiple brah mic scripts since the early formal syntactic work by @xcite and is the first such library de signed based on an observation by @xcite that the fundamental organizing principles of the brahmic scripts can be algebraically formalized. in particular, all the core components of our li brary (inverse romanization, normalization and wellformedness) are compactly and efficiently represented as finite state transducers. such for malization lends itself particularly well to runtime or offline integration with any finite state process ing pipeline, such as decoder components of in put methods @xcite , text normalization for automatic speech recognition and texttospeech synthesis @xcite , among other natural language and speech applications. ## brahmic scripts: an overview the scripts of interest have evolved from the an cient brāhmī writing system that was recorded from the 3rd century bce and fell out of use by the 5th century ce @xcite . the main unit of lin ear graphemic representation in brahmic scripts is known by its traditional sanskritderived name aks ̣ara. as bright (1999) notes, it is often trans lated as "syllable" although it does not bear di rect correspondence to a syllable of speech, but rather to an orthographic syllable. the structure, or "grammar" of an aks ̣ara is based on the follow ing common principles: an aks ̣ara often consists of a consonant symbol 𝐶, by default bearing an unmarked inherent vowel or attached diacritic (de pendent) vowel sign 𝑣 (𝐶 𝑣 ); but it may also be an independent vowel symbol 𝑉 , or a consonant sym bol with its inherent vowel "muted" by a special virama diacritic ∅ (𝐶 ∅ ). in any of these preceding scenarios, the base consonant 𝐶 can be replaced by a consonant cluster where all but the last conso nant lose their inherent vowel. when the individ ual component consonants of the cluster combine to form a composite form, precluding the use of an overt virama diacritic, this is known as a "conso nant conjunct" (e.g., @xcite . the elements of the aks ̣ara grammar described above can be grouped into several natural classes. the sizes of the core classes are shown in ta ble 1 for each writing system and its correspond ing iso 15924 identifier in uppercase format @xcite . the major classes are the independent vow els (e.g., the devanagari diphthong औ), the depen dent vowel diacritics (e.g., the gujarati ◌ી), and the consonants (e.g., the gurmukhi ੜ). another im portant class consists of the coda consonant sym 3 here, surrounding the consonants in square brackets will serve to indicate that the enclosed consonants form a conjunct together. visual legacy sequence nfc normalized ऩ na nukta (u+0928 u+093c) nnna (u+0929) क़ qa (u+0958) ka nukta (u+0915 u+093c) unicode normalization unicode defines sev eral normalization forms which are used for check ing whether the two unicode strings are equiv alent to each other (unicode @xcite . in our library we support normalization form c (nfc) which is well suited for comparing visu ally identical strings. this normalization gener ally converts strings to the equivalent form that uses composite characters. visual normalization as was mentioned above, an aks ̣ara may be represented by multiple unicode character sequences and the goal of nfc normal ization is to convert them to their unique canonical form. however, there are many unicode character sequences that fall outside the scope of nfc algo rithm. we provide visual normalization that, in ad dition to providing the nfc functionality, also sup ports transforming such legacy sequences. some of the rules are provided as "do not use" tables by the unicode @xcite that recommends transformations from legacy sequences to their cor responding canonical form, such as devanagari { अ (u+0905), ॅ (u+0945) } → ॲ (u+0972). we also included transformations for visually identical se quences (under many implementations) which are commonly found on the web, such as devanagari { ऐ (u+0910), े (u+0947) } → ऐ (u+0910). foot_3 wellformedness check a wellformedness ac ceptor verifies whether the given text is readable in a particular script or not. it would be hard for the native reader to visually parse the text if the script rules are not followed. for example, the reader does not expect two vowels signs on a single con sonant and such a thing may not even be possible to reasonably draw. furthermore, unlike the latin script, acronyms are not written using arbitrary let ter sequences, they are formed only as a sequence of aks ̣ara. our approach verifies whether the text is a sequence of wellformed aks ̣ara using the gram mar described above. reversible iso transliteration iso 15919 rep resents a unified 8bit latin transliteration scheme for major south asian brahmic scripts @xcite . since it has not been updated with the characters that were introduced to the unicode standard af ter 2001, we have added additional mappings, with some examples shown in languagespecific logic several south asian languages often share the same script with some, often minor, languagespecific differences. our library supports languagespecific customizations that can be combined with languageagnostic script logic. for example, the modern bengali-assamese script (beng) is shared by both bengali and assamese languages, among others @xcite . for both of these languages our library provides customizations, foot_4 such as the transformations required for visual normal ization of assamese that transform bengali let ter ra into its assamese equivalent when it par ticipates in a consonant conjunct (which gener ally occurs when following or preceding virama, e.g., { র (u+09b0), ◌্ (u+09cd) } → { ৰ (u+09f0), ◌্ (u+09cd) }). ## the finitestate approach the brahmic script manipulation operations described above have a natural intepretation grounded in formal language theory. we treat the text corpus in a given script as a set of strings over some finite alphabet σ that defines a set of admissable script symbols. the set of zero or more strings is known as language which, in its simplest (regular) form, can be succintly described (or recognized) by a finite state automaton (fsa) or acceptor @xcite . two simple fsas that represent the gujarati word દસ are shown in figure 1 , where the top automaton represents the word over an alphabet of unicode code points for gujarati, while the bottom one represents the same string over the corresponding byte symbols in utf8 encoding (unicode consortium, 2019). our library supports both representations. the aks ̣ara grammar outlined in the previous section can be expressed via elementary formal op erations on the fsas that describe grammar con stituents. such settheoretic operations include union (∪), concatenation (+) and closure, where closure is defined as an arbitrary natural number of concatenations of a language 𝐿 over σ with it self, either accepting an empty input {𝜖} or not, denoted 𝐿 * (kleene star) and 𝐿 + (kleene plus), respectively @xcite . these operations represent nontrivial automata which are compiled offline resulting in compact and ef ficient representations. a simplified process for constructing the automaton 𝒲 to perform the well the rest of the operations on the brahmic scripts, namely the normalization and transliteration, in volve modifications of the brahmic script inputs. such operations are naturally expressed by finite state transducers (fsts), which are a generaliza tion of the fsa concept used to encode string string relations (or transductions), by modifying the automata arcs to have pairs of labels from in put and output alphabets, instead of single labels. a trivial romanization in our representation of the two sinhala words එක (⟨eka⟩, "one") and ෙදක (⟨deka⟩, "two") is shown in figure 3 . note the "vocalization" of the final consonant by insertion of a schwa via an input 𝜖transition. also note that the path accepting the second word is longer. the word ෙදක consists of three aks ̣ara and requires modification of the inherent vowel by the depen dent vowel in order to produce ⟨de⟩. the basic operations on the fsas outlined above also extend to the fst case and allow for similarly succinct final compiled representa tions @xcite , such as the simplified con struction of the iso romanization transducer ℐ for converting from brahmic scripts to latin alpha bet, shown in figure 4 . an important extension of fsas and fsts are the weighted finite state au tomata (wfsas) and transducers (wfsts) @xcite that equip each arc in the automaton or transducer with a weight, thus allowing optimiza tion and search algorithms to compute the costs of distinct paths, which can be used to determine their relative importance. we use weights in some of our grammars to indicate the relative priority of a par ticular aks ̣ara modification. for example, in fig ure 4 , the paths corresponding to consonants fol lowed by dependent vowels (line 6) have priority require: fsts: consonant, vowel, vowel_sign, coda, standalone, virama. finally, the transducers representing language specific customizations of a particular script op eration are compiled by composing the generic languageagnostic transducer, such as the devana gari visual normalizer, with the transducer rep resenting transformations that capture language specific use of the script, e.g., devanagari for nepali. ## system details and demo the core of the nisaba brahmic script manipula tion library resides under the brahmic directory of the distribution. in this section we provide de tails for how to build and use the library and also explore its application to visual normalization of wikipediabased text in 9 of these scripts. prerequisites we use bazel (google, 2020) as a primary build environment. for compiling the automata and transducers we employ pynini foot_5 , a python library for constructing finitestate gram mars and for performing operations on wf sts @xcite ). in addition, the library depends on thrax foot_6 , an older relative of pynini, that provides a custom gram mar manipulation language for wfsts @xcite . although thrax has been mostly superseded by pynini, we still rely on some of its utilities for unit testing and its c++ run time components. at their core, both pynini and thrax depend on the openfst library foot_7 for the im plementation of most wfst algorithms @xcite . the overall depen dency diagram is shown on the lefthand side of figure 5 (the minimal dependency on thrax is in dicated by a dotted arrow). at build time, bazel pulls in these dependencies remotely from their re spective repositories. compiling the transducers figure 6 presents the sequence of steps to compile the transduc ers, including downloading the repository (line 2), compiling the library and its artifacts (line 5) and running the unit tests (line 7). the artifacts are compiled by bazel using pynini and consist of the finite state archive (far) files that contain collec tions of wfsts @xcite . for each of the four brahmic script operations we generate two far files: one for wfsts over the byte al phabet, and another over the unicode code point alphabet. 10 each far file contains ten script specific transducers whose names correspond to the uppercase iso 15924 script codes. since the transliteration operation is bidirectional, the name of each scriptspecific transliteration transducer has the prefix from_ for the nativetolatin direc tion, and to_ for the inverse. the numbers of states (𝑁 𝑠 ) and arcs (𝑁 𝑎 ) of the resulting transliteration (ℐ), nfc (𝒩), visual normalization (𝒱) transduc ers and wellformedness acceptors (𝒲) for each script and alphabet type are shown in ## conclusion and future work we presented finitestate automatabased utilities for processing the major brahmic scripts. the fi nite state transducer formalism provides an effi cient and scalable framework for expressing brah mic script operations and is suitable for many nlp applications, such as those reported in @xcite and @xcite , which may ben efit from the reduction in "noise" present in unnor malized text. in the future, we will continue to im prove the support for existing scripts and extend our work to other brahmic scripts.