Compare strings of different size/length

I'm getting a huge headache in coding a procedure to determine similarities between two strings and so the index of the best matching into a more than 10,000 elements cell.

the i-th element of the first cell matrix is something like:

str1= 'Class music n. 12 160b' 

which is the element I want to search into the other matrix. The correspondant matching element of the second matrix, e.g., is:

str2= 'Classical musical n. 12 160beats'

and so on.

I wish to find a procedure to distinguish whether this couple is the most similar with respect to all the others (others can be like

str3 = 'Techno music n. 7 120beats' 
str4 = 'Rock disco n. 12 140beats'
str5 = 'Punk metal n. 18 180 beats'

or even more different).

I wish to find the index in the cell matrix where

str2

variable is, in order to manipulate it.

I've been trying several approaches, but with none of them I achieved consistent results.

Would you be able to assist me in this?

Thank you

M

[Michele Rizzato]

I wish to add that with a Levenshtein fuction I have two issues:

• procedure is REALLY slow (since i calculate with editdistance the distance for all element of the matrix, then i select the index of the minimum);

• I get few false positives (and those sometimes are VERY far from the current solution of the problem).

My aim is to get a unique index, corresponding to the most precise match (not necessarily an exact match thou).

Thank you,

M

[Rik]

You need something like fuzzy matching.

What you can do to achieve something like this manually is to parse each char array to its constituents: break it up into the style, number and speed. Then you can more easily attempt to match.

[Michele Rizzato]

I also add i've been trying to separate the single words into different string, making all the occurrances lower case in order to avoid case sensitive issues, but i'm stuck in the middle and can't find a correct way to proceed.

I wish to find a quick general solution for this.

[Stephen23]

To solve this task you need to define what "most similar" means mathematically. As you have probably discovered, using a naive metric (e.g. the Levenshtein distance) is quite possibly not the most suitable (e.g. short strings can match because they have a close edit distance even if most characters are different, whereas you want to match based on the meaning of the content (certainly not a trivial task)).

Possibly you could rely on some prior knowledge to preprocess the strings (e.g. replace all abbreviations with the equivalent full words) and then try measuring the edit distance. For example:

Does 'Class ' always represent 'Classical ' ?

Does 'b' at the end always represent 'beats' ?

etc.

You could trivially define these replacements using a regular expression and then calculate the edit distance.

[Michele Rizzato]

Even if would be a long process to indentify all the abbreviations, then it will be easier to calculate the edit distance, true.

But my problem is that edit distance works with positional matching so i'd need a procedure that can identity the matching words even when put randomly into the string.

Is that possible?

[Michele Rizzato]

I've also tried to use FPAT for a fuzzy approach, but strangely what i get with

fpat(str1,str2)

is the following:

 struct with fields:

      magic: 'FPAT'
        ver: '25-Oct-2004 20:49:37'
       time: '04-Dec-2020 15:16:21'
    runtime: 0.0053
        par: [1×1 struct]
       mode: 'ALL patterns'
       npat: 0

Answer 1

[Stephen23]

in1 = 'Class music n. 12 160b';
in2 = {'Classical musical n. 12 160beats','Techno music n. 7 120beats','Rock disco n. 12 140beats','Punk metal n. 18 180 beats'};
rgx = {'([Cc])lass(\s+)','\d+b$'};
rpl = {   '$1lassical$2','$&eats'};
tm1 = regexprep(in1,rgx,rpl);
tm2 = regexprep(in2,rgx,rpl);
edd = editDistance(tm1,tm2)

edd = 1×4

2 12 13 16

●

[~,idx] = min(edd);
in2{idx}

ans = 'Classical musical n. 12 160beats'

[Michele Rizzato]

Thank you Stephen, this works great in the particular case, but it's not a solution i can apply to the general case. If next time i want to search for:

'Techno music n. 7 120beats'

i should write a different code

[Stephen23]

"i should write a different code"

No, that is not the idea at all: there should be just one list of all abbreviations and their replacements (this assumes that you have this prior knowledge) which you can apply to all strings. What I showed is just a demonstration using your example data, but you will need to complete it with all abbreviations. You can then use the same code for any string that you want to match.

If the order of the words can be "random" as you wrote, then first replace the abbreviations, split the words, sort the words alphabetically (or alphanumerically), join the words, and finally measure the edit distance:

in1 = 'Class music n. 12 160b'; % string you want to match
in2 = {'Classical musical n. 12 160beats','Techno music n. 7 120beats','Rock disco n. 12 140beats','Punk metal n. 18 180 beats'};
rgx = {'([Cc])lass(\s+)', '\d+b$'};
rpl = {   '$1lassical$2','$&eats'};
fun = @(s)join(sort(split(s))); % or use NATSORT (must be downloaded)
tm1 = fun(regexprep(in1,rgx,rpl));
tm2 = cellfun(fun,regexprep(in2,rgx,rpl));
edd = editDistance(tm1,tm2)

edd = 1×4

2 12 13 18

●

[~,idx] = min(edd);
in2{idx}

ans = 'Classical musical n. 12 160beats'

Answer 2

[Sibi]

try this,

[Rik]

I was just about to remove your answer from the spam filter. Feel free to put the code in your answer again. If it gets flagged, I'll remove the flag.

[Michele Rizzato]

Thank you Sibi

but not sure your code takes into account that abbreviations may occur in the original matrix

[Sibi]

R='T m n. 7 120b';

code will work for this one also.

[Michele Rizzato]

Looks like it works great but if I start from

R='Techno alpha music n. 7 120beats'

it says that index exceed the number of array elements (6)