Function that shortens a String based on a term/abbreviation mapping

Question

I have a function that takes a description as a String and returns a shortened version of the description.

The shortening is done by checking if a word matches the key of the HashMap<String,String> map and replaces the word by its abbreviation defined as the value in the HashMap. If the word cannot be found it in the HashMap it will not be replaced (it stays the same). If the value of a word is <remove> the word will be removed from the new description.

There can be multiple abbreviations for the same word.

Example:

AUTOMATIC GAIN CONTROL --> AGC

CONTROL --> CTRL

In any case the function should always take the abbreviation which takes the most words.

Consider this example mapping:

AUTOMATIC GAIN CONTROL --> AGC

CONTROL --> CTRL

IDENTIFIER --> ID

THE --> <remove>

The input String:

The Automatic Gain Control identifier value

will result in the output String:

AGC ID value

The String's in the HashMap are all uppercase and the abbreviation in the output String should also be uppercase. However, any word that was not found in the HashMap should stay the same as it was in the input String.

My function seems to do the task correctly but I'm not sure if it could have been written better and/or more efficiently.

private static HashMap<String,String> map = new HashMap<String, String>();

public static String shortenText(String input){

    ArrayList<String> listUpperCase = new ArrayList<String>(Arrays.asList(new String(input).toUpperCase().split(" ")));
    ArrayList<String> list = new ArrayList<String>(Arrays.asList(input.split(" ")));

    //Remove any words that map to <remove>
    for (int i=0;i<list.size();i++){
        String value = map.get(listUpperCase.get(i));
        if (value!=null){
            if(value.equals("<remove>")){
                list.remove(i);
                listUpperCase.remove(i);
            }                   
        }
    }
    //Replace words by their abbreviation
    StringBuilder builder = new StringBuilder();
    for (int i=0;i<list.size();i++){
        StringBuilder tempBuilder = new StringBuilder();
        String longestStringToShort="";
        int count=0;
        //Find abbreviations for terms with multiple words
        for(int k=0;k<list.size()-i;k++){
            tempBuilder.append(" "+listUpperCase.get(i+k));
            if(k==0) tempBuilder.deleteCharAt(0);
            String value = map.get(tempBuilder.toString());
            if (value!=null){                   
                longestStringToShort = value;
                count = k;                                      
            }
        }
        if (!longestStringToShort.equals("")){
            builder.append(" "+longestStringToShort);
            i=i+count; 
        }
        else builder.append(" "+list.get(i));

    }

    builder.deleteCharAt(0);
    return builder.toString();

}

Answer 1

Some observations (partly covered in @RoToRa's answer):

• A placeholder String such as "<remove>" doesn't communicate at a glance whether a subsequence can be removed or not. Consider if you are scanning through your code:

  map.put("Another Bored Cat", "ABC");
  map.put("Another Bad Coral", "<remove>");
  map.put("Another Berry Can", "ABC");
  

  You may miss out that "Another Bad Coral" needs to be removed, purely by looking at the length of the line. It's arguably easier to read as such:

  map.put("Another Bored Cat", "ABC");
  map.put("Another Bad Coral", "");
  map.put("Another Berry Can", "ABC");
  

  In this case, it also removes the ambiguity (as unlikely as that may seem initially) that "Another Bad Coral" will be substituted with "<remove>".

• Not particularly efficient uses for StringBuilder, especially when you builder.append(" " + aString) when you can do builder.apppend(' ').append(aString). Furthermore, you are also creating a StringBuilder for every tokenized word.

• Related to the previous point, your explicit concatentation of " " characters forces you to repetitively do builder.deleteCharAt(0), which also leads to buggy derivation.

• Usage of Map/HashMap can be enhanced so as to reduce the explicit looping that you are currently doing by tokenizing the input String. As you mentioned, you want to "takes the most words as the key in the HashMap", so if there's a way to actually iterate in that order from the Map...

Alternative implementation (Java 8 features ahead)

You can then use a TreeMap with a suitable Comparator implementation to persist and iterate with. For example:

private static final Comparator<String> KEY_COMPARATOR = (s1, s2) -> {
    int diff = Integer.compare(s2.length(), s1.length());
    return diff == 0 ? s1.compareToIgnoreCase(s2) : diff;
};

Or in the form of an anonymous class:

private static final Comparator<String> KEY_COMPARATOR = new Comparator<String>() {

    @Override
    public int compare(String s1, String s2) {
        int diff = Integer.compare(s2.length(), s1.length());
        return diff == 0 ? s1.compareToIgnoreCase(s2) : diff;
    }
};

This literally does what is required: if the lengths of both Strings are the same, we'll use a case-insensitive comparison between the both of them, else we simply rank the longer String to be greater than the other. This means that a Map such as:

private static final Map<String, String> MAPPER = getMapper();

private static Map<String, String> getMapper() {
    Map<String, String> mapper = new TreeMap<>(KEY_COMPARATOR);
    mapper.put("THE", "");
    mapper.put("AUTOMATIC", "AUTO");
    mapper.put("ZOOKEEPER", "ZK");
    mapper.put("AUTOMATIC GAIN CONTROL", "AGC");
    mapper.put("IDENTIFIER", "ID");
    return mapper;
}

Will give us the following desired iteration order:

// MAPPER.forEach((key, value) -> System.out.printf("%s => %s\n", key, value));
AUTOMATIC GAIN CONTROL => AGC
IDENTIFIER => ID
AUTOMATIC => AUTO
ZOOKEEPER => ZK
THE => 

With this Map implementation, the overall solution is half-complete. What is left is to replace any matching keys (as a subsequence) in the input String with the shortened value. For this, you can consider using regular expressions to perform the substitution on just one instance of StringBuilder:

private static String shorten(String input) {
    StringBuilder result = new StringBuilder(input);
    MAPPER.forEach((key, value) -> {
        Matcher matcher = Pattern.compile("(?i)\\b" + key + "\\b").matcher(result);
        while (matcher.reset().find()) {
            result.replace(matcher.start(), matcher.end(), value);
            if (value.isEmpty() && result.length() != 0) {
                result.deleteCharAt(Math.max(0, matcher.start() - 1));
            }
        }
    });
    return result.toString();
}

• Use a case-insensitive ((?i)) Pattern instance to apply on the StringBuilder via Pattern.matcher(CharSequence). The \\b word boundary is important to make sure we only match on a complete expression demarcated by whitespaces.
• Loop through each match, taking care to reset() the Matcher instance first.
• Replace the contents of the StringBuilder instance using the results matcher.start() and matcher.end().
• For cases where we are removing text, we also need to remember to delete the previous character, or the first, so long as the StringBuilder instance is non-empty.

Unit-testing

In case this is not done yet, remember to unit test this method too! For example, using a combination of TestNG and Hamcrest matchers library to perform the required assertions:

@Test
public void testInput() {
    String test = "There is the Automatic Automatic Gain Control Zookeeper Identifier";
    assertThat(shorten(test + " " + test), 
                    equalsTo("There is AUTO AGC ZK ID There is AUTO AGC ZK ID"));
    // the middle whitespace is effectively trimmed away
    assertThat(shorten("the the"), equalsTo(""));
    assertThat(shorten("The Automatic Gain Control identifier value"),
                    equalsTo("AGC ID value"));
}

Answer 2

I don't the time for an extensive review. Here some quick remarks:

Use better variable names. Just map for the main replacement map is bad.

Your code does have a bug. Try running shortenText("THE THE");. Hint: Removing elements from a list while looping over it is dangerous.

Don't keep two lists with the same contents. Just use one list and use toUpperCase where needed.

new String(...) is almost always unnecessary.

I would expect to be able to remove whole phrases with spaces, instead of just single words, just like you can replace phrases with an abbreviation. Actually you shouldn't need to handle the search for removement phrases differently than replacement phrases, just the action you take after finding them would be different.

Using a placeholder String such as "<remove>" is a bad idea. It would be best to use a different type, or in this simple case just use null.

Splitting everything into words is unnecessarily complex. Just search the phrases in the input string (for example with the String method indexOf).