# Language Detection

The aim of this project is to analyse a text in order to detect its language. For that, we propose to find the occurrence frequencies of the characters in the text. We will interpret these frequencies as a probability distribution that will be used for several purposes:
- detect the language of the text by comparing its distribution with several probability distributions of known languages (english, french, spanish, ...)
- compress the text by using a compression algorithm (_Huffman_ coding) based on its probability distribution.

From a programming point of view, the first objectives of this project are to learn the basics in Python (variables, conditions, loops, ...). The concept of function will also be seen. Simultaneously, we will try to learn to decompose a problem into several problems.

## Table of content
- [_Requirements_](#requirements-toc)
- [_Running the project_](#running-the-project-on-isaes-computers-toc)
- [_Assignment_](#assignment-toc)
- [_Q1. Occurrence frequency analysis_](#q1-occurrence-frequency-analysis-toc)
- [_Q2. Enhanced occurrence frequency analysis_](#q2-enhanced-occurrence-frequency-analysis-toc)
- [_Q3. Influence of the text length on the quality of detection_](#q3-influence-of-the-text-length-on-the-quality-of-detection-toc)
  - [_Q3.1._](#q31-toc)
  - [_Q3.2._](#q32-toc)
- [_Q4. Compression with Huffman_ (_optional_)](#q4-compression-with-huffman-toc-optional)
- [_Upload your work to the LMS_](#upload-your-work-to-the-lms-toc)

![Languages](./assets/languages.jpg)

---

## Requirements [[toc](#table-of-content)]
you should have completed the following notebooks before starting this project:
- the [basics of the Python language](https://gitlab.isae-supaero.fr/mae/learn-python#the-basics-of-the-language)
- how to [read and write to text files and write functions](https://gitlab.isae-supaero.fr/mae/learn-python#reading-text-files-and-writing-functions)

## Running the project on ISAE's computers [[toc](#table-of-content)]

see the [_Locally on ISAE's computers_ section](https://gitlab.isae-supaero.fr/mae-ac/learn-python#locally-on-isaes-computers-toc)
of TP0, using `https://gitlab.isae-supaero.fr/mae-ac/language-detection.git` as the URL and `code .` as the final command.

## Assignment [[toc](#table-of-content)]
you and anyone looking at your code should be able to run the following command without getting any errors:
```shell
make test
```

> :bulb: **Note**
>
> for any question x, you can run `make qx` to see the output of this question, e.g. `make q1` or `make q4.2.1`

If make is not installed, you can also run the command:
```shell
pytest
```

See the makefile in the project to specify the test you want to run.

## Q1. Occurrence frequency analysis [[toc](#table-of-content)]
> :exclamation: **Important**
>
> there are no tests to run in this section, you can relax... for now :wink:

Your first objective is to find the occurrence frequencies of the letters of the alphabet in a text.

:pencil: Open the [`occurrence_frequencies.py`](src/occurrence_frequencies.py) script in your editor
of choice and fill it. This file already contains the steps to follow :
- Add the following line at the start of your script, which will allow the use of the type annotations below
```python
from typing import Dict
```
- Create a dictionary containing the letters with the occurrences equal to 0
- For each letter in the text, increment the corresponding entry of the dictionary
- Normalize the values of the dictionary in order to have frequencies (the sum is equal to 1)

## Q2. Enhanced occurrence frequency analysis [[toc](#table-of-content)]
:file_folder: Create a new file called `enhanced_occurrence_frequencies.py` in the `src/` directory.

:gear: you can run the `make test` command and see 6 failing tests. These tests should hopefully
pass at the end of this question!

Now we will use the [_Wuthering Heights_ by Emily Bronte](data/english_wuthering_heights.txt) text and analyze it.

:pencil: You should now be able to answer the following questions:
1. Write a function `read_text` to read a text file and return a string text containing only lower case characters.
> - arguments:
>   1. filename: `str`
> - return: `str`

2. Apply this function to the file [`data/english_wuthering_heights.txt`](data/english_wuthering_heights.txt) and store its content in the variable `my_text`.
3. Write a function `compute_occurrence_frequencies` to compute the occurrence frequencies of the letters of a string `alphabet` in the string `text`. This function returns the corresponding dictionary.
> - arguments:
>   1. text: `str`
>   2. alphabet: `str`
> - return: `Dict[str, float]`

4. Apply this function to the string `characters = "abcdefghijklmnopqrstuvwxyz"` and the string `my_text`. Store the output dictionary in the variable `english_of` (english occurrence frequency).
5. Compute the occurrence frequencies of french, spanish and german languages by respectively using the files [`french_madame_bovary.txt`](data/french_madame_bovary.txt), [`spanish_don_quijote.txt`](data/spanish_don_quijote.txt) and [`german_kritik_der_reinen_vernunft.txt`](data/german_kritik_der_reinen_vernunft.txt).
6. The Kullback–Leibler (KL) divergence defines a kind of distance between two probability distributions. If we consider two distributions $P=(p_1, \ldots,p_n)$ and $Q=(q_1, \ldots,q_n)$:
$$D_{KL}(P,Q)=\sum_{i=1}^{n} p_i \log_2 \frac{p_i}{q_i}$$

> :bulb: **Note**
>
> All the $q_i$ must be strictly positive. If some of them are equal to zero, do not consider the corresponding symbol.

Since the KL divergence is not symmetric, you can symmetrize it by computing the absolute value of the average of $D_{KL}(P,Q)$ and $D_{KL}(Q,P)$.

> :bulb: **Note**
>
> You need the `log` and the `fabs` functions. Since there are not loaded by default, you must add the line `from math import log,fabs` at the beginning of your file.

Write a function `kl_divergence` that takes two probability distributions in the form of previously computed dictionaries and returns the symmetric _Kullback-Leibler_ divergence.
> - arguments:
>   1. first probability distribution: `Dict[str, float]`
>   2. second probability distribution: `Dict[str, float]`
> - return: `float`

7. Compute the KL divergence between the different languages.
8. Write a function `detect_language` which is able to determine the language used in a text file. The idea is just to compute the occurrence frequencies of the characters in the text file and to compute the KL divergences with the occurrence frequencies of the various languages.
> - arguments:
>   1. text: `str`
>   2. references languages: `Dict[str, Dict[str, float]]`
>   3. alphabet: `str`
> - return: `str`

---

## Q3. Influence of the text length on the quality of detection [[toc](#table-of-content)]
:file_folder: Create a new file `src/text_length.py`.

The accuracy of the language detector depends on the length of the input text. The objective of this exercise is to evaluate this accuracy according to the length of the text.

##### Q3.1. [[toc](#table-of-content)]
For each text length, evaluate the probability of good detection and plot the result with `matplotlib`.

> :bulb: **Note**
>
> the details of this question have been intentionally left as an exercise to the students.
> it's time for you to shine and experiment what you think would be a good approach.
>
> if you get really stuck or have no idea where to begin, feel free to ask your professor for some insights :wink:

##### Q3.2. [[toc](#table-of-content)]
To try improve this result, you can try to capture the redundancy of a language in the sequences of 2 (or more) letters. For that, consider the pairs of consecutive letters as a symbol (of course, the size of your alphabet of sybols will increase) and do the same analysis to check if you can improve the detection results.

## Q4. Compression with Huffman [[toc](#table-of-content)] (_optional_)
:file_folder: Create a new file `src/data_compression.py`.

The analysis of the occurrence frequencies of the characters in the languages shows that there is a strong variability between the characters. This shows that there is some "redundancy" in the languages. In other words, this means that it is possible to compress the languages by using these occurrence frequencies.

Basically speaking, the maximum level of compression that can be obtained with the occurrence frequencies is given by the entropy. The entropy gives a bound on the average number of bits used to code a symbol. In this part, we will first compute the entropy, and then verify that we can obtain such level of compression with the Huffman algorithm.

1. The entropy is a mathematical concept that measures the "amount of information" of a probability distribution. If we consider a variable which takes its values in the set {$a_1, a_2, \ldots, a_n$} with the probabilities $p_i=p(a_i)$, for $i=1,\ldots,n$, then the entropy  $H(X)$ is defined by :
    $$H(X)=-\sum_{i=1}^{n} p_i \log_2 p_i$$
    If you want to learn more on the entropy concept, which has strong applications in compression, error correcting codes and cryptography, have a look on [this video](https://www.khanacademy.org/computing/computer-science/informationtheory/moderninfotheory/v/information-entropy) :)

    By assuming that the occurrence frequencies obtained of englishOF are representative of the occurrence probabilities of the characters in the english language, compute the entropy of the english language. For that :
    1. add the line `from enhanced_occurrence_frequencies import read_text, compute_occurrence_frequencies, detect_language` that allows you to use the functions defined in the previous file.
    2. In order to be fair in the evaluation of the compression, you need to integrate all the possible characters, instead of just the letters. So, to generate the string characters which contains the considered characters, copy-paste the code :
    ```python
    characters = [chr(i) for i in range(128)]
    ```
    and re-compute the associated dictionaries

    3. write a generic function that computes the entropy from any distribution probability represented by a dictionary.
2. Compute the entropies of french, spanish and german languages.
3. The Huffman algorithm is a famous compression algorithm which is one of the components of current audio and video compression standards. A short presentation of this algorithm is given in [this video](https://www.khanacademy.org/computing/computer-science/informationtheory/moderninfotheory/v/compressioncodes). The objective here is not to program it (lack of time...) but rather to use an implementation. This implementation is provided in the file [`huffman.py`](src/huffman.py). You can find on this files the main steps of the algorithm :
    1. the construction of the tree according to the probabilities with `build_huffman_tree`
    1. the generation of the code with `generate_code`
    1. the compression of the text with `compress`
    1. the decompression with `decompress`

    Use these algorithm to compress and decompress the language files (do not forget to `import` it).

    1. Verify that the entropy gives a lower bound of the average number of bits used to code the characters. This number of bits can be obtained from the output of the compression algorithm. Note that this output is not a binary file, but a string of characters '0' and '1'... So the average number of bits per characters can be obtained by
    $$\frac{\textrm{number of characters in the compressed file}}{\textrm{number of characters in the initial text file}}$$
    Observe the "beauty of the math" by verifying the accuracy of the entropy bound !!
    1. Evaluate the compression ratio by considering that each character of the text files is encoded on 7 bits. Thus the compression rate is given by :
    $$\frac{7\times \textrm{number of characters in the initial text file}}{\textrm{number of characters in the compressed file}}$$
4. How to improve the level of compression ? The occurrence frequencies of each character only capture the redundancy of the characters, but not the one between consecutive characters... So, you can do the same exercice by analyzing the occurrence frequencies of all  2-letter (or more) words. This should allow you to capture more redundancy of the text and then to improve the compression ratio.

## Upload your work to the LMS [[toc](#table-of-content)]
- open a terminal
- go into the folder containing your project
- use the `zip` command to compress your project
```shell
zip -r project.zip . -x "venv/**" ".git/**"
```
- upload the ZIP archive to the [LMS](https://lms.isae.fr/mod/assign/view.php?id=116608&action=editsubmission)
