-1
\$\begingroup\$

Recently I have been developing a library for Java which provides utility functions for arrays, strings, etc.. While researching string similarity algorithms, I managed to write one of my own. I am curious as to if anyone has come across a similar approach or if it is a commonly known one. The code is sampled below.

public static int temprovichDistance(String ref, String check) {
    if (ref == null || check == null) return -1;
    if (ref.equals(check)) return 0;
    if (ref.length() == 0 || check.length() == 0) return -1;
            
    // if negative, then ref is shorter than check
    int lendiff = ref.length() - check.length();
    int dist = 0;

    for (int i = 0; i < ref.length(); i++) {
        char r = ref.charAt(i);
        char x = 0;

        if (lendiff < 0) x = check.charAt(i);
        else if (i < check.length()) x = check.charAt(i);
        else break;

        if (r == x) continue;
        else {
            if (lendiff > 0) ref = remove(ref, r);
            else if (lendiff < 0) check = remove(check, x);
                    
            if (r != x) dist++;
        }
    }

    if (dist == 0 && lendiff != 0) dist += Math.abs(lendiff);

    return dist;
}

Thanks again to anyone that proves an answer!

Edit:

I managed to take a different approach which seems to work in all cases:

public static int temprovichDistance(String referenceString, String comparisonString) {
        if (referenceString == null || comparisonString == null) return -1;
        if (referenceString.equals(comparisonString)) return 0;
        if (referenceString.length() == 0 || comparisonString.length() == 0) return -1;
            
        int dist = 0;
            
        for (int i = 0; i < referenceString.length(); i++) {
            int tmp = 0;
            for (int j = 0; j < comparisonString.length(); j++) {
                if (referenceString.charAt(i) != comparisonString.charAt(j)) tmp++;
                else continue;
            }
            if (tmp == comparisonString.length()) dist++;
        }

        return dist == 0 ? dist + Mathf.abs(referenceString.length() - comparisonString.length()) : dist;
    }

Thanks again for any comments <3

\$\endgroup\$
1
  • 7
    \$\begingroup\$ What does your algorithm do that makes it different from other difference/similarity distance algorithms like Hamming, Minkowski, Levenshtein and LCS? \$\endgroup\$
    – Mast
    Jan 6 at 21:28

2 Answers 2

6
\$\begingroup\$

This method has no javadoc, and I have no idea what values are returned when. Apparently -1 is a magic number meaning something didn't work right? That's typically done using exceptions, so callers have some clue as to what went wrong.

ref and check are not a great variable names. Perhaps referenceString and comparisonString would be better? r and x are pretty much meaningless. Descriptive names are more readable than abbreviations.

If both strings are "" then the distance is zero, but if one string is "" and the other isn't, that's an error? That fails the principle of least surprise, and needs to be documented or the logic corrected.

Its easier to read the validations on the inputs if they're grouped by input, not by validation type.

While curly braces are technically optional, they should pretty much never be omitted. They add to readability and prevent future errors.

The easier way to loop over the shorter of two strings is to Math.min() the two lengths and use that as the index. This significantly cleans up the logic around stopping the loop.

In most cases, it's easier to read if blocks if the conditional code is on its own lie. It is especially hard to read when the else block is in curly braces.

The if () continue else {} would be better with the condition inversed. If they're not equal, do stuff. This is because it's at the end of the loop anyway.

This if (r != x) doesn't make sense. The code can't get into the else block unless they're unequal. Checking again does nothing.

The remove() method is not provided, but destructively modifying input parameters should be avoided. Perhaps turning them into locally assigned StringBuilders would be better? Then you have removal options on the class.

I don't see what remove() is trying to do. If it's destructively removing from the parameters, then your looping is skipping over some characters in the string. It would be helpful if you added it for review. It would also be helpful if you added an explanation of the algorithm you're trying to implement.

Using dist += is confusing - it looks like addition, but this is really an assignment of a value, since dist is zero at this point. Prefer assignment.

There's no real value in checking if lengthDifference != 0, since Math.abs will return 0 in that case.

Using a trinary for the return value might be easier to read.

If you made all these changes, your code might look more like:

public static int temprovichDistance(String referenceString, String comparisonString) {
    if ((referenceString == null) || referenceString.isEmpty()) {
        throw new IllegalArgumentException("referenceString may not be null or empty.");
    }
    if ((comparisonString == null) || comparisonString.isEmpty()) {
        throw new IllegalArgumentException("comparisonString may not be null or empty.");
    }
    if (referenceString.equals(comparisonString)) {
        return 0;
    }

    int maxIndex = Math.min(referenceString.length(), comparisonString.length());

    // if negative, then referenceString is shorter than comparisonString
    int lengthDifference = referenceString.length() - comparisonString.length();
    int distance = 0;

    for (int i = 0; i < maxIndex; i++) {
        char referenceChar = referenceString.charAt(i);
        char comparisonChar = 0;

        if (referenceChar != comparisonChar) {
            if (lengthDifference > 0) {
                referenceString = remove(referenceString, referenceChar);
            } else if (lengthDifference < 0) {
                comparisonString = remove(comparisonString, comparisonChar);
            }
            distance++;
        }
    }

    return (distance == 0) ? Math.abs(lengthDifference) : distance;
}
\$\endgroup\$
1
  • 5
    \$\begingroup\$ Ok, let's step back. You provided no set of requirements, no test cases, and omitted some code, and you're surprised that my example explaining my suggestions doesn't exactly behave the same way as your original code. You express your surprise in a rude and condescending way. Good luck getting more reviews! \$\endgroup\$
    – Eric Stein
    Jan 9 at 13:57
0
\$\begingroup\$

Sorry, posibly I mised something, but this looks like convertion of some C/C++ code to Java. Other then C++ Java is strict OO, so you need to put that int temprovichDistance inside a class:

public class TemprovichDistance{

  public static int temprovichDistance(String referenceString, String comparisonString){
    ...
  }
}

Also would replace this code:

if (referenceString == null || comparisonString == null) return -1;
if (referenceString.equals(comparisonString)) return 0;
if (referenceString.length() == 0 || comparisonString.length() == 0) return-1;

by this one:

if (referenceString == null || comparisonString == null || referenceString.length() == 0 || comparisonString.length() == 0) return -1;
if (referenceString.equals(comparisonString)) return 0;

Also a bit confused about this part of Code:

if (r == x) continue;
else {
    if (lendiff > 0) ref = remove(ref, r);
    else if (lendiff < 0) check = remove(check, x);
            
    if (r != x) dist++;
}

Checking if (r != x) make no sence at that place, as it similar to if (true). This complete code can be simplified to:

if (r != x){
        if (lendiff > 0) ref = remove(ref, r);
        else if (lendiff < 0) check = remove(check, x);        
        dist++;
}

Also what that remove should do and where it comes from?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.