Latest revision as of 03:14, 6 May 2023

What I Did

Throughout this semester, I was introduced to several tools we used in class to develop language technologies like hfst, lexd, and Apertium. I did not understand what was happening behind the simple files we created in class and how they were converted to output, and using them felt difficult or not intuitive. I decided to use Python to build my own analyser for Amis, a threatened Austronesian language indigenous to Taiwan that I worked with all semester long. After taking CS21 Introduction to Computer Science last year, I wanted to challenge myself to tackle a complex coding problem and devote myself to improving my Python skills. By building a tool myself in Python, I have full control over all parts of the tool and its functionality.

I wanted a program that, like the .lexd file I created earlier in the semester, would use Amis grammar patterns to put together morphemes to form words and show tags.

The first step was to assemble a list of morphemes. Luckily, our lexd file already had lots of morphemes listed out for me to use. Entries in our lexd file look something like this:

aku:aku     <pers><sg><p1>:
isu:isu     <pers><sg><p2>:
ingra:ingra <pers><sg><p3>:
ira:ira     <pers><sg><p3>: # Possible fix to pronoun spelling issue
ita:ita     <pers><pl><p1><incl>:
ami:ami     <pers><pl><p1><excl>:
amu:amu     <pers><pl><p2>:
angra:angra <pers><pl><p3>:

Each line has multiple instances of the morpheme, several tags, and sometimes even comments. This is unfortunately not so useful for me. I need to be able to identify the actual Amis roots, the tags, and get rid of any comments. I wrote a Python program, text_formatter.py, which takes care of this for me. The resulting text looks something like this:

aku,pers,sg,p1
isu,pers,sg,p2
ingra,pers,sg,p3
ira,pers,sg,p3
ita,pers,pl,p1,incl
ami,pers,pl,p1,excl
amu,pers,pl,p2
angra,pers,pl,p3

We've gotten rid of any extra white space, extra characters, comments, and we ended up with a more predictable format where it is clear that the Amis text comes first, followed by comma separated tags. This format will be much easier to use to populate a Python data structure.

Next, I created a data structure in Python that would be able to organize this text. My data structure separately stores the bit of Amis at the front, a list of tags, and it keeps track of the root so we can add prefixes and suffixes. I stored several lists of these data structures as variables in a dictionary, with the keys being category of morphemes, such as noun roots, verb tenses, or case markers. Finally, I implemented patterns to stitch morphemes together, while also concatenating any associated tags. The basic architecture of a pattern is as follows:

1. List the desired roots on their own.
2. Identify which types of morphemes are optional and compile a list of them.
3. For each of these options, append to all items in the first list a copy of itself with the new morpheme attached.

Pseudo Code:

forms = [all of the roots]
options = [several dictionary keys]
for each option{
    for each form{
        append to forms: a copy of the form with options attached
    }
}

The innermost loop adds more items to the list of forms, so the number of iterations of the outermost loop dynamically increases.

Links to my Code

My code, as well as all of the data mentioned above can be found in the following Github repository: https://github.com/lchien1/chien-ami-analysis

Results

The complete output of my analyser can be found in the same github repository, at: https://github.com/lchien1/chien-ami-analysis/blob/main/output/output.txt

My analyser uses for the most part, the same Amis morphemes and patterns that we implemented before using HFST. However, the coverage analysis for HFST is complex in how it treats individual tokens and what qualifies as a token (numbers? punctuation?). Therefore, comparing their coverage is trivial. However, it is still useful to evaluate coverage over a corpus as a sanity check.

The Amis corpus can be found at: https://github.swarthmore.edu/Ling073-sp23/ling073-ami-corpus

To check coverage over a corpus, I created a new Python program called analyze_corpus.py. The program reads the words from the corpus (which is a text file) and stores them in a set (you can read about sets here: https://www.digitalocean.com/community/tutorials/python-set). A set here is preferable to using a list because sets store unique values, and we do not want the program to look up the analysis of a form more than once. Then, the program reads the dictionary of forms from a .csv file that was created by previously by ami_analyser.py. The program iterates through the set and looks up the analysis for each word. Therefore, the time complexity is O(n) by the number of words in the corpus.

Efficiency of Python Analyser

To test efficiency, I used the built in time and resource libraries.

• For ami.corpus.basic.txt (9.4kb)
  • Coverage: 62/510 unique forms
  • Time to compile: 0.2 seconds
  • Memory Required: 58.9 megabytes
• For ami.corpus.large.txt (80.7kb)
  • Coverage: 235/2925
  • Time: 1.3 seconds
  • Memory: 59.4 megabytes
• For ami.wiki.20230320.txt (2.93 MB)
  • Coverage: 597/50245
  • Time: 22.5 seconds
  • Memory: 217.9 megabytes

Efficiency of Prior HFST Analyser

To test, use:

cat ../ling073-ami-corpus/ami.corpus.basic.txt | /usr/bin/time apertium -d . ami-morph 

• For ami.corpus.basic.txt (9.4kb)
  • Average time to compile: 0.33 seconds
  • Memory Required: 12.9 megabytes
• For ami.corpus.large.txt (80.7kb)
  • Time: 0.32 seconds
  • Memory: 13.3 megabytes
• For ami.wiki.20230320.txt (2.93 MB)
  • Coverage: 597/50245
  • Time: 1.58 seconds
  • Memory: 13.1 megabytes

Comparison

Coverage is not calculated the same way for these two analysers. However, because these two transducers contain mostly the same library of morphemes and similar patterns, it makes sense to compare the efficiency of each against the other. Because the Python program stores the entire dictionary of forms for searching, it is both memory inefficient and slower. The time complexity for HFST is O(n) based on the number of letters it has to build. The Python analyzer stores whole forms and searches them, so it is O(n) based on the number of words.