{'fraction_non_alphanumeric': 0.03317535545023697, 'fraction_numerical': 0.006802341789796488, 'mean_word_length': 4.559826410415375, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Semi-Automatic Indexing of Multilingual Documents

With the growing significance of digital libraries and the Internet, more and more electronic texts become accessible to a wide and geographically disperse public. This requires adequate tools to facilitate indexing, storage, and retrieval of documents written in different languages. We present a method for semi-automatic indexing of electronic documents and construction of a multilingual thesaurus, which can be used for query formulation and information retrieval. We use special dictionaries and user interaction in order to solve ambiguities and find adequate canonical terms in the language and adequate abstract language-independent terms. The abstract thesaurus is updated incrementally by new indexed documents and is used to search document concerning terms in a query to the document base.


Introduction
In order to get extensive and precise retrieval of textual information, correct and consistent analysis of incoming documents is necessary. The most broadly-used technique for this analysis is indexing. An index file becomes an intermediate representation between a query and the document base.
One of the most popular structures for complex indexes is a semantic net called thesaurus. The nodes are single or composite terms and the links are semantic relationships between these terms.
Bruandet [4,5] has developed an automatic indexing technique which was extended by Gammoudi [6] for optimal thesaurus generation for a given set of documents. The nodes are rectangles where the left side contains a set of terms and the right side the set of documents indexing the terms. Higher rectangles in the thesaurus contains more specific term sets and less documents. One extension of this technique is the algorithm of Pinto [14] which permits an incremental addition of index terms of new incoming documents, updating the Thesaurus.
We show in this paper how this extended version of Gammoudi's technique can be used in an environment with multilingual documents and queries whose language need not be the same as that of the searched documents. The main ideas are the using of monolingual dictionaries in order to, with the user's help, eliminate ambiguities, and an abstract, language independent thesaurus. The terms of a query are also converted to the abstract terms in order to find the corresponding documents.
Whereas most work on Multilingual (or Translingual) Information Retrieval concentrate on query processing [16], our focus is on the indexing of digital documents.
In the next section we give basic mathematical definitions and notions of thesauri, including our definition of a multilingual rectangular thesaurus. The following section 3 shows the procedure of term extraction from documents, finding the abstract concept and the term-document association and inclusion of the new rectangle in the existing rectangular thesaurus. Section 4 shows the query and retrieval environment and, finally, section 5 discusses some related work and concludes the paper.

Rectangular Thesaurus: Basic Concepts
The main concept used for thesaurus construction is the binary relation. A binary relation can be decomposed in a minimal set of optimal rectangles by the method of Rectangular Decomposition of a Binary Relation [6, 3]. The extraction of rectangles from a finite binary relation has been extensively studied in the context of Lattice Theory and has proven to be very useful in many computer science applications..
A rectangle of a binary relation R is a pair of sets (A, B) such that A × B ⊆ R. More precisely

Definition 1: Rectangle
Let R be a binary relation defined from E to F.
A binary relation can be represented by different sets of rectangles. In order to gain storage space the following coefficient is important for the selection of an optimal set of rectangles representing the relation.

Definition 2: Gain in storage space
The gain in storage space of a rectangle RE=(A,B) is given by: where Card(A) is the cardinality of the set A.
The gain becomes significant if Card(A) > 2 and Card(B) > 2, then g(RE) > 0 and grows with Card(A) and Card(B). On the other hand, there is no gain (g(GE)<0) if Card(A) =1 or Card(B) =1. The notion of gain is very important because it allows us to save memory space, in particular when we need to store a large volume of terms.

Definition 3: Optimal Rectangle
A maximal rectangle containing an element (x, y) of a relation R is called optimal if it produces a maximal gain with respect to other maximal rectangles containing (x, y).

Definition 4: Rectangular Graph
Let "≤≤" be a relation defined over a set of rectangles of a binary relation R, as follows: ∀ (A1,B1) e (A2, B2) two rectangles of R: We call (R, ≤≤) a Rectangular Graph.
Note that "≤≤" defines a partial order over the set of rectangles.

Definition 5: Lattice
An ordered set (R, <) is called a lattice if each subset X ⊆ R has a minimal upper bound and a maximal lower bound.

Proposition 1:
Let R ⊆ E × G be a binary relation. The set of optimal rectangles of R, ordered by "≤≤" (R, ≤≤) is a lattice with a lower bound (∅, G) and an upper bound (E, ∅).

Semantic Relations
Semantic relations are the basis for the transformation of a rectangular graph in a rectangular thesaurus. They connect the nodes of a rectangular thesaurus in order to find more generic, more specific, or other related rectangles. There are three kinds of semantic relations in a rectangular thesaurus: hierarchical relations (generic and specific), equivalence relations (synonyms and pseudo-synonyms), and neighborhood relations.
The hierarchical relations are based on the following definition:

Definition 6: Hierarchical relation
Let RE i = (A i , B i ) and Re = (A j , B j ) be two optimal rectangles of a relation R. RE i is a generic of RE j iff: If the domains are terms and the co-domain are document identifiers, then A i indexes more documents than A j . The rectangles of interest in this paper will all be of this format, i.e. relating terms to documents. Each term in a rectangle is the representative of an equivalence relation of synonyms. The (representative) terms in the rectangle are called pseudo-synonyms. Note that two terms are pseudo-synonyms if they index the same set of documents.   Non hierarchical relations between rectangles occur when two rectangles have some information in common but none of them is a generic of the other [12].

Definition 8: Non-hierarchical relation
Let RE i = (A i , B i ) and RE j = (A j , B j ) be two optimal rectangles of R. RE i is a neighbor RE j if and only if the following conditions hold:

Multilingual Rectangular Thesaurus
We extend the definition of multilingual thesaurus of Sosoaga [16] in order to include the notion of contexts that allow the elimination of ambiguities.
A multilingual thesaurus is a classification system defined as MTh = (V, n, r; L 1 , C 1, t 1 , L 2 , C 2 , t 2 , ..., L k , C k , t k ) composed of a unique set of abstract concepts (V), a set of lexicons {L 1 ,.., L n }, a set of contexts {C 1 , .. , C k } a set of functions t i : L i × C i → V which associate to each term of the lexicon in a given context a unique abstract term. The hierarchical and non-hierarchical relationships are given by n (narrower term) and r (related term).  A rectangular multilingual thesaurus is a multilingual thesaurus where the elements of V are optimal rectangles and the relations n and r follow the definitions of hierarchical and nonhierarchical semantic relations between rectangles, defined above.
In order to construct rectangles with representative terms, we can decompose each function t in two parts t 0 and t 1 , with t(x, c) = t 1 (t 0 (x, c)). The function t 0 is responsible for the selection of the canonical representative between the synonyms in a given context and t 1 is an injective function that determines the abstract term associated with the original term in a given language.

Simplified representation of a rectangular thesaurus
The hierarchical connected nodes of a rectangular thesaurus contain a lot of redundancy, since if (A 1 ,B 1 ) ≤≤ (A 2 , B 2 ) we now that A 1 ⊆ A 2 and B 2 , ⊆ B 1 . For large document bases this become prohibitive. For this reason we apply the simplification algorithm of [6] and if (A 1 ,B 1 ) ≤≤ (A 2 , B 2 ) the rectangle (A 2 , B 2 ) is represented by (A 2 -A 1 , B 1 -B 2 ), without loss of information content.

Construction of a Rectangular Multilingual Thesaurus
The construction of a Rectangular Multilingual Thesaurus is done in three steps: • Term extraction from one or more documents and determination of the abstract concepts, using a monolingual dictionary (semiautomatic indexing); • Generation of one or more optimal rectangles; • Optimal insertion of the new rectangles into the existing thesaurus.

Semi-automatic indexing
The construction of a rectangular thesaurus referencing a set of electronic documents in a natural language begins with the extraction of relevant terms contained in the document. Our semi-automatic method allows the user to eliminate ambiguities interactively.
The first step consists of words selection, stopword elimination and, for significant words, finding of the abstract term. As shown in Figure  3.1, two dictionaries are used for this step. The first, a dictionary of term variations, contains all lexical variations of words in a language and determines its normal form. Compound words, such as 'Data Base' or 'Operating System' must be considered as single terms, since in other language  should be associated to a single abstract term code. These are identified by a look-ahead step if the dictionary identifies a candidate compound word.
Having found the normal form of a term, the main dictionary is then used to find the abstract language-independent term, depending on the context.
In the main dictionary, the column "Representative" and the list of "Related terms" will be used in the construction of the thesaurus in a given language for query formulation (see section 4 below).
In the next subsection we show how, based on Bruandet's method, the association of (abstract) terms is determined. The co-occurrence of pairs of terms is analyzed thus allowing the determination of the binding force between the terms and the choice of candidates for rectangle construction. Since the complete analysis is done at the abstract concept level, term variations and synonyms are considered to represent the same concept.

Measure of the term-term connections
Let C be the set of concepts associated with the terms extracted from a set of documents. We want do determine a measure of the contextual proximity of two concepts. This measure is based on the works of Attar e Fraenkel [2]. The i-th occurrence of a term 1 x of a vocabulary T, written as w x (i), is defined by: where ND x (i) is the number of the document containing x; NF x (i) the number of the phrase in the document; NT x (i) the position of the term in the phrase.
For each pair of terms (x, y), we define the distance d between the i-th occurrence of x and the j-th occurrence of y: 1 We use the word 'term' as a synonym of 'concept' in the following discussion. The binding force between two terms is a function F given by the inverse of the distance between the terms:

is an experimentally obtained constant defined below
It is important to consider the grammatical category of the terms. In most cases the categories of interest are nouns, adjectives and verbs. For each language we can determine the distance between the grammatical categories, and this distance will be used to determine the constant t in the formula above.

t(x, y) = DIST[CAT(x), CAT(y)]
where DIST[x, y] is the distance between the grammatical categories of x and y. The correction factor k can be used if we want to avoid that pairs of terms that occur only once be included in the association. The parameter n is defined by experimentation and a typical value is 2 [5]. Higher values of n give more weight for pairs occurring frequently and discard pairs with few occurrences.
We show in Figure 3.1 an example of the computing of M(t1,t2) using a text on object orientation. (t2) b(t1,t2) f(t1,t2

Generation of optimal rectangles
The values of the association measure M are stored in a binary term-term matrix. Values of M less than a specific constant are set to 0 while the others are set to 1. Note that the matrix is symmetrical and the diagonal can be disregarded. This fact can be used to better choose how to store the information.
After selecting the relevant terms for each document, based on the association measure, the original binary relation between terms and documents is reduced to its significant terms only.
We apply the method of rectangular decomposition of a binary relation R [6] in order to obtain the optimal rectangles. The main steps in this method are the following: 1. Decompose R in n elementary relations ER 1 , .., ER n 2. Select, in parallel, for each elementary relation ER i the set of optimal rectangles; 3. Select, for each ER i , the minimum optimal rectangles that cover the relation; 4. Eliminate as many redundant elements as possible in the optimal rectangles.
Although the general maximal rectangle selection problem is NP-hard, the heuristics given in [6] are O(n 3 ).

Updating the rectangular thesaurus
Each rectangle obtained in the previous steps relates a set of terms to a set of documents. If we are processing a single document, one rectangle is generated with the significant terms indexing that document. We must now insert the new rectangles in the existing abstract rectangular thesaurus. Figure 3.2 shows the rectangular thesaurus for a document base, where the abstract terms of the domains of the rectangles have been exchanged by natural ones. Since it is in simplified form, term redundancy has been eliminated.

Figure 3.2: Document thesaurus
Note that in a rectangular thesaurus, we can identify several cardinality levels, due to the cardinality of the rectangle domain. These levels vary from 0 to n, where n is the total number of terms in the thesaurus. Each new rectangle must be placed in the corresponding level. In the example, the second level has cardinality 10 and the third level has cardinality 21, since 11 terms have been added to the level below.
The following algorithm, from [14], provides the insertion of a new rectangle in an existing rectangular thesaurus. We consider the thesaurus in its original definition, without simplification. Considering the simplification is straightforward.

Information Retrieval
The purpose of an information retrieval system is to return to the user a set of documents that match the keywords expressed in the query. In our system we present an interface, using the user's preferred language, representing the thesaurus of concepts occurring in the document database. This thesaurus includes synonyms, related terms and hierarchical relations.
The dictionary-like form of the interface is not as user-friendly as generic natural language interfaces, but it avoids the well known problems with natural languages and guarantees fast access to the documents searched for. As reported by LYCOS, typical user queries are only two or three words long [17]. In a rectangular thesaurus, the retrieval process consists of finding a rectangle Ri = Ci x Di, such that Ci is a minimal domain containing the set of terms from the query Q. If Ci ≠ Q the user can receive feedback from the system concerning other terms which index the retrieved documents. This fact is identified as a Galois connection in [6]. Note that we can obtain several rectangles matching the query. On the other hand, the user can eliminate some terms from the query in order to obtain more documents.
As can be seen in the figure, the prototype allows one to chose a language and as he/she is selecting the terms, the systems lists the corresponding documents.

Conclusion
Most work on thesaurus construction uses automatic indexing of a given set of documents [5] [6] [18] [19] and, in the case of a multilingual framework, use machine translation techniques applied on the query [17]. In [14] an incremental version of the approach on automatic generation of rectangular thesauri of Bruandet and Gammoudi has been developed. The main contribution of this paper is to integrate the incremental approach with a dictionary-based multilingual indexing and information retrieval and to propose an interactive ambiguity resolution. This approach eliminates problems of automatic indexing, linguistic variations of a single concept and restrictions of monolingual systems. Furthermore the problem of terms composed of more than one word has been solved with a look-ahead algorithm for candidate words found in the dictionary.
It is clear that the interaction with the user is very time-consuming. But, it seems to be a good trade-off between the precision of manual thesaurus construction and the efficiency of automatic systems. With an 'apply to all' option on can avoid repeating conflict resolutions.
The indexing approach used has two drawbacks which have not been solved up to now: 1. The hierarchical relations in the rectangular thesaurus are purely syntactic, i.e. more composed terms are more specific that less composed ones; 2. The relevance analysis of pairs of term completely eliminates single terms of phrases. As a result, a term can occur very frequently in a document but, if it appears associated to distinct terms in different phrases, it could be eliminated as an indexing candidate.
One possible solution to the first problem is to use of a richer dictionary for term analysis. If the dictionary has thesaurus-like information, this can be used for the construction of the rectangular term-document thesaurus. For the second problem, a word counter, running in parallel with the indexing, could help the inclusion of single terms.