Code for the search-and-copy algorithm
Switch branches/tags
Nothing to show
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.


Search-and-Copy Algorithm


This is a python implementation of the search-and-copy algorithm defined in


To start the algorith, extract the zip file, open a terminal, move in the search_and_copy directory, and type in
$ python

You will be given a table that tells you what features (f1, f2, f3) correspond to each segment (a,b,c,d,e). This can be modified as you wish, just make sure to respect the one space convention between each +, -, / symbols. Note also that /f means that f is underspecified for the feature f; you can ask specifically for a segment to be underspecified. 

You will then be asked to provide a string composed of those segments; this is the string we will be performing the algorithm on.

After that, the string will be parsed and it will return a list of sets of features corresponding to each segment of your string.

Then you will be asked to enter both an initial and terminal condition. You can separate them by commas or spaces or all together in one string, e.g. "+f1, +f2" or "+f1 +f2" or "+f1+f2". Then enter the direction to take the search in.

The algorithm will perform the search part of it and return a list of pairs of indices (starts at 0) corresponding to the starting segments and the segments that the search algorithm found, i.e. if (3, 4) is part of the list, then you know that the 4th segment found what it was looking for at the 5 segment, and this one satisfied both initial and terminal conditions.

You will now have to chose between the original copy algorithm, a replace algorithm or an "inverse" copying one. In either case, you will have to enter the feature you want to be shared or copied and the one to be taken out if you use the replace algorithm. Enter _f if you want the target to copy whatever value the feature f takes in the trigger (think of this as alphaf). Note that underspecification can also be shared in our system. Enter also the condition to be satisfied by the trigger (list of features).

Note that the replace algorithm will assign /f to our segment in case where the argument _f is passed, no matter what was there before.

Also, the only different between "copy" and "inverse copy" is that in the latter the condition to check is on the target, not the trigger.

The algorithm will then give you a list of sets of features resulting from the copy algorithm.

It will end by translating those sets of features into a string of segments by looking up in the table; if no segment can be found, the algorithm will tell you and write * as the segment.



$ python
This is what the table of features looks like
- f1 f2 f3

a + + /

b + / -

c + - /

d - - +

e + + -

Enter the phonological string on which to perform the algorithm
- abcdeadcebcda
Corresponding sets of features:
[{+f1, +f2, /f3}, {+f1, /f2, -f3}, {+f1, -f2, /f3}, {-f1, -f2, +f3}, {+f1, +f2, -f3}, {+f1, +f2, /f3}, {-f1, -f2, +f3}, {+f1, -f2, /f3}, {+f1, +f2, -f3}, {+f1, /f2, -f3}, {+f1, -f2, /f3}, {-f1, -f2, +f3}, {+f1, +f2, /f3}]
Enter the initial condition
- +f1     
Enter the terminal condition
- -f3
Enter the direction of the search (l/r)
- r
Results of the search algorithm by index (-1 = no match):
  [(0, 1), (1, -1), (2, 4), (3, 4), (4, -1), (5, -1), (6, -1), (7, 8), (8, 9), (9, -1), (10, -1), (11, -1), (12, -1)]
Enter the feature to be shared
- _f2
Enter the condition to be satisfied by the trigger
- -f3
Set of features after copy:
[{+f1, /f2, /f3}, {+f1, /f2, -f3}, {+f1, +f2, /f3}, {-f1, +f2, +f3}, {+f1, +f2, -f3}, {+f1, +f2, /f3}, {-f1, -f2, +f3}, {+f1, +f2, /f3}, {+f1, /f2, -f3}, {+f1, /f2, -f3}, {+f1, -f2, /f3}, {-f1, -f2, +f3}, {+f1, +f2, /f3}]
Final phonological string:
- No segment in database for {'f1': '+', 'f2': '/', 'f3': '/'}
No segment in database for {'f1': '-', 'f2': '+', 'f3': '+'}