The verification and resolution of formal analogies between strings focuses on the character sequences, disregarding the underlying semantics of the sequences. Our approach to these two tasks employs an algorithm based on edit distance. A previous version was limited in that it provided only a single solution for an analogy equation, even when multiple valid solutions existed. We enhance the algorithm to generate all possible solutions. The previous algorithm traversed edit distance matrices only once. Consequently, it could only yield one solution for an analogy puzzle, even in cases of multiple solutions were viable. In order to deliver all possible solutions for analogies, we introduce a recursive approach. By recursively exploring all traces in the edit distance matrices, our newer version is capable of generating and outputting all feasible solutions.
In this paper, we deal with formal analogies between strings, i.e., sequences of characters, like
the ones described in [
Analogy between strings can be applied in the field of natural language processing for tasks
like transliteration [
In the previous work by [
In the work conducted by [
The Shufle algorithm proposed by [
In Table 1, it is evident that the complexity algorithm outperforms the Distance algorithm in terms of accuracy. This may be attributed to the fact that the Distance algorithm fails to deliver certain solutions, which results in a lower overall performance.
By correcting the limitation of the Distance algorithm, it is hoped that an increase in accuracy will be obtained.
In the Sigmorphon Analogy Dataset, the provided answers for certain analogy puzzles do not encompass all potential solutions. This is illustrated by the following example. asked : ask :: seemed :
⇒ = seem or seme
The dataset suggests that the correct answer to this analogy is “seem”. It does not consider “seme” as a solution. However, theoretically, “seme” satisfies the criteria for solving analogies adopted by the Distance algorithm and should be identified as a potential answer. The previous version of the Distance algorithm outputs only one of the solutions. Consequently, there is a need to propose an algorithm that would generate the two possible answers for this analogy, including the one that is not recognized by the dataset as a solution.
⇒ = ?
In order to deliver all possible solutions for an analogy puzzle, we first examine why the previous algorithm delivers only a single solution. Let us consider an example analogy puzzle:
The processing of the Distance algorithm involves several steps. Firstly, it checks whether
the analogy puzzle satisfies a specific constraint, namely whether all the letters in the string
appear either in the string or teh string . Once this constraint is met, the algorithm
proceeds to compute edit distance matrices [
Then the algorithm computes the edit distance traces [
The established correspondence can be visualised in the following table, where actions that consist in outputting one character at a time in the solution, are taken according to the correspondence between the two traces, relying on the directions followed along the traces.
diagonal diagonal diagonal
diagonal horizontal diagonal
do copy copy copy
As a result, the algorithm delivers the solution . The algorithm explores the traces only once and stops. Consequently, it does not output other possible solutions: and .
To get the solution , the algorithm needs to follow the following steps, indicated in the following table, similar to the previous one above.
diagonal diagonal diagonal
do horizontal copy a diagonal copy b diagonal copy a
The traces that have been followed in this table, are other paths that allow to still get the minimal edit distances between and on the one hand, and between and on the other hand. The edit distance matrices are the same matrices as above, but the traces are diferent. Here, in fact, only the trace between and is diferent.
The new trace shown here is not computed by the algorithm, although it corresponds to a minimal edit distance between the strings involved in the analogy puzzle. The reason for the algorithm to provide only one solution is that it simply does not produce and explore all possible traces within the matrices.
To address this limitation, we propose to implement a recursive version of the Distance algorithm. By adopting a recursive approach, the algorithm will go beyond the initial trace it ifnds and backtrack to the beginning, thereby exploring alternative traces. This modification will allow the algorithm to consider multiple traces and generate a other solutions for the same analogy puzzle.
It is important to note that while the main idea of the algorithm remains the same, the proposed change lies in the implementation of the algorithm. The recursive version enhances the algorithm’s capability to explore and generate a more comprehensive set of traces, thus improving the overall solution output for the analogy puzzle, that is its recall.
We evaluate our work by performing experiments on the previously introduced Sigmorphon Analogy Dataset. In addition, we use automatically generated data, for which we control the number of solutions, so as to ensure that the new version of the Distance algorithm actually outputs the exact number of possible solutions for a given analogy puzzle and that the solutions are exact.
The Distance algorithm relies on a definition of analogy given in [
Based on the observation at the foundation of the definition of analogy between strings by distance [10, p. 731], and similarly, based on the definition by shufle [ 16, p. 123], we can state that, if an analogy has solutions, all the characters in should appear in and at least once. Consequently, generating analogy puzzles which have no solution can be done by the following procedure which basically enforces a character in to appear in neither nor in . – Step 1: Randomly generate a string . – Step 2: Randomly select a character, delim, in which will not appear in or . – Step 3: Randomly generate strings and that do not contain the character selected in –
Step 2:.
Below is an instance of the above generation process to get an analogy without any solution. – Step 1: ←
abcd. – Step 2: delim ← – Step 3: , ←
bc, efgc ( and do not contain delim = a).
With these values, the following analogy puzzle has no solution: abcd : bc :: efgc :
⇒ = no solution
As mentioned earlier, in the case of an analogy with solutions, every character present in string must also appear in either string or string . Consequently, to create an analogy with only one solution that is the empty string, it sufices to create and from by distributing each character in either in or in , in the same order. As a result, all characters from are found in or . In this setting, for the shufle explanation, ∙ = ∙ implies that is the empty string. For the distance explanation, because of the counts of characters in and being equal to those in and , this also implies that is the empty string.
A degenerated case of the above is to split into two parts, the left and the right parts, i.e., is a prefix of and is the remaining sufix of . This makes the analogy . : :: : .
Drawing upon the approach of generating analogy puzzles with an empty string solution, it becomes feasible to incorporate additional sub-strings within both and . These sub-strings are concatenated in the sequential order of their insertion into and , ultimately forming the solution to the analogy puzzle, denoted as . • Divide into a prefix and a sufix
′ and ′, i.e., = ′.′. • Create additional sub-strings that do not share any character with .
• Insert the additional sub-strings into ′ or ′.
In the last step, the following constraints are crucial in guaranteeing the uniqueness of the solution: • No additional sub-string should be added as a sufix of ′; • No additional sub-string should be added as a prefix of ′.
To justify these constraints, consider the following analogy puzzle: abcd : ab :: cd : Here, the prefix is ′ = and the sufix is ′ = . Let us denote the additional sub-strings by and . We insert into the middle of string ′. We insert at the beginning of string ′, which does not respect the constraint given above. Clearly, because of that, the obtained analogy puzzle has possibly several solutions: abcd : aMb :: Ncd :
⇒ = any string in M ∙ N
Hence, the procedure for generating analogy puzzles that possess a unique solution can be outlined as follows: • no sub-string is inserted as a sufix of the prefix • no sub-string is inserted as a prefix of the sufix ′. ′.
Here is a generation instance following the above procedure: – Step 1: Generate a string = abcd. Select the position of a character, for instance, "c" to divide into prefix abc and sufix d. – Step 2: Create three sub-strings op, mn and opmn. – Step 3: Insert the sub-strings respecting the constraints. For instance, get = amnbopc and = dopmn. is necessarily the concatenation of the sub-strings in the order they have been inserted in the prefix and sufix of , which is unique. Hence, is unique. As a result the obtained analogy puzzle has only one unique solution: abcd : amnbopc :: dopmn :
⇒ = mnopopmn
As explained in the section regarding the generation of analogy puzzles with only one solution, certain constraints serves as a means of ensuring solution uniqueness. However, in the absence of such constraints, alternative methodologies can be employed to generate analogy puzzles with multiple solutions.
There are primarily two constraints we previously mentioned, which are: 1. Position:
No additional sub-string should be added as a sufix of ′, and no additional sub-string should be added as a prefix of ′. 2. Character:
Create additional sub-strings that do not share any character with .
Let us consider a slight variation of the example given in section 3.2.2 that ignores the constraint on position: abcd : abM :: Ncd :
⇒ = any string in M ∙ N
In this analogy puzzle, we denote the additional sub-strings by and . We add as the sufix of ′ and as the prefix of ′, which has the consequence that the analogy puzzle has potentially several solutions.
Hence, a first possible procedure for generating analogy puzzles that possess several solutions can be outlined as follows: – Step 1: Randomly generate a string and select a position to divide into prefix ′ and sufix ′. – Step 2: Create two sub-strings randomly, each without any of the characters in . To ensure that . contains two or more elements, we impose that each of the two sub-strings contains at least two diferent characters. – Step 3: Add one sub-string as the sufix of ′ and another as the prefix of ′ to get and .
Here is an example that ignores the character constraint: abcd : aOb :: cMdNcMdN :
⇒ = any string in OcMdNcMdN ∖ cd
In this analogy puzzle, we denote the additional sub-strings by , , and . We insert into string ′, insert and into string ′ and repeat ′ several times to get . This creates an analogy puzzle with several solutions because of the multiple possibilities to erase from .
Hence, a second procedure for generating analogy puzzles that possess several solutions can be outlined as follows: – Step 3: Insert the sub-strings into ′ and ′ and get and ′′, respecting the constraints: • no sub-string is inserted as a sufix of the prefix • no sub-string is inserted as a prefix of the sufix ′. ′. – Step 4: Repeat ′′ any number of times to get .
We run both the previous version of the Distance algorithm and its new recursive version on the above-mentioned data sets, i.e., the Signmorphon ananlogy datatset and the datasets of analogy puzzles with zero, one only or several solutions. We measure their processing time, precision, recall, and F-measure.
The results given in Table 2 show that, while the recursive version may exhibit a longer processing time in average compared to the previous version, its recall is 100% on the automatically generated testsets, and higher (98.5%) than the previous version (92.2%) on the Sigmorphon Analogy Dataset. We conclude that the recursive version successfully delivers almost all of the solutions of the analogy puzzles contained in our datasets.
We also compare the results to the methods in [
The comparative analysis on the Sigmorphon Analogy Dataset reveals that, except for one language, Spanish, the new version of the Distance algorithm introduced in this paper consistently outperforms the three alternative methods. Thanks to its higher recall, this new version demonstrates superior performance.
This observation suggests that the relatively poorer performance of the previous Distance algorithm can be attributed to its failure to capture all the possible solutions for certain analogy previous recursive previous recursive previous recursive previous recursive
Sigmorphon Zero solution One solution Several solutions
Average time ( s) Algorithm
Dataset
Precision (%) Recall (%) F-measure puzzles. The absence of these solutions significantly impacted the recall. Conversely, the new recursive algorithm addresses this limitation by delivering a more comprehensive set of solutions, resulting in a higher recall for almost all languages, and consequently a higher average recall.
The precision of the new recursive algorithm on the Sigmorphon Analogy Dataset is not 100% due to the nature of the approach, which outputs multiple solutions in many cases, whereas the Sigmorphon Analogy Dataset only expects a single solution.
For instance, consider the following analogy: fakura¯tu : ustra¯liyya¯tu :: faku¯run :
⇒ = ustra¯liyyun or ustrliyya¯un
According to the Sigmorphon Analogy Dataset, the expected answer for this analogy is ustra¯liyyun. However, theoretically, the answer ustrliyya¯un is also a possible solution. Although it satisfies the definition of analogy on which our algorithm is based, it is not considered a valid solution within this particular linguistic context.
As mentioned in the section discussing the production of the automatically generated analogy puzzles, these additional solutions can be seen as “noise” since they do not align with the general notion of what constitutes a solution. Evaluating the efectiveness of our approach becomes problematic when using only the Sigmorphon Analogy Dataset, as it primarily focuses on a single expected solution rather than capturing the full scope of potential solutions. Testing solely on the Sigmorphon Analogy Dataset may not provide a comprehensive evaluation of whether our goals have been achieved.
In this paper, we built upon an existing algorithm for solving analogies. Our objective was to make this algorithm deliver all solutions for an analogy puzzle when there are multiple solutions. To accomplish this, we introduced recursivity to systematically explore all possible edit distance traces in the representation of analogy puzzles by edit distance matrices. Thanks to this we are able to enumerate all possible solutions of an analogy puzzle.
To evaluate the efectiveness of our proposal, we generated a dataset comprising analogies with diferent characteristics, i.e., cases with no solution, cases with one solution, and cases with multiple solutions. We presented the methods adopted to automatically produce analogy puzzles in all these diferent cases. The generated dataset allowed us to conduct an analysis on specific cases and ascertain the ability of our recursive version of the algorithm to deliver all existing solutions. Experiments demonstrated that our proposed new version of the algorithm successfully achieves this goal.
To summarize, by introducing a recursive approach we could expand the scope in solutions and could increase the performance of the Distance algorithm on the dataset of analogy puzzles extracted from the Sigmorphon Analogy Dataset.
This paper has been partially supported by the JSPS project Kakenhi Kiban C no 21K12038 entitled “Theoretically founded algorithms for the automatic production of analogy tests in Natural Language Pocessing”.