5
\$\begingroup\$

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();

}
\$\endgroup\$
  • 1
    \$\begingroup\$ Will there be similar replacements? E.g. replacing AUTOMATIC GAIN CONTROL with AGC and AUTOMATIC with AUTO? \$\endgroup\$ – h.j.k. Aug 11 '15 at 9:12
  • \$\begingroup\$ If I understand your question correctly, yes. One word can be a part of the key of multiple abbreviations. See my example with AUTOMATIC GAIN CONTROL and CONTROL. The function should always use the abbreviation that takes the most words as the key in the HashMap \$\endgroup\$ – isADon Aug 11 '15 at 9:18
  • \$\begingroup\$ @isADon ah yes, didn't see your CONTROL example... thanks for the clarification anyways. :) \$\endgroup\$ – h.j.k. Aug 11 '15 at 9:18
  • 1
    \$\begingroup\$ Ever thinking of using a Trie? Only that for you it's word-based instead of character based. \$\endgroup\$ – Edwin Aug 12 '15 at 3:34
2
\$\begingroup\$

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"));
}
\$\endgroup\$
  • \$\begingroup\$ Very neat implementation but unfortunately I am forced to use Java 6. I marked it as the correct answer anyway since I did learn a lot from it and it does the task correctly. Can you tell me why builder.apppend(' ').append(aString) is better than doing builder.append(" " + aString)? \$\endgroup\$ – isADon Aug 12 '15 at 8:20
  • 1
    \$\begingroup\$ Tip: it's not that hard to retrofit the Java 8 forEach() method (just loop explictly using for (Entry<String, String> ...) or convert the KEY_COMPARATOR lambda to an anonymous class (new Comparator<String>() { ... }). ;) \$\endgroup\$ – h.j.k. Aug 12 '15 at 8:58
  • \$\begingroup\$ Whenever you do " " + aString, an implicit StringBuilder is also used for this concatenation. It's simply easier and more efficient to let the existing StringBuilder instance add the whitespace character (efficiency), then aString so that it can also figure out by itself whether it needs to resize or not. \$\endgroup\$ – h.j.k. Aug 12 '15 at 9:00
  • \$\begingroup\$ Thank you for the information! Can you show me how to change the lambda to an anonymous class? I'm not able to get the syntax right for some reason \$\endgroup\$ – isADon Aug 12 '15 at 9:36
  • 1
    \$\begingroup\$ @isADon see updated answer. \$\endgroup\$ – h.j.k. Aug 12 '15 at 9:51
1
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ Why do you suggest not splitting my input string in to words? I'm not sure I understand your implementation with indexOf. Just to clarify: My map has a size of about 500. 90% of the entries are mappings between a single word and its abbreviation. The input String has a maximum length of 50-60 characters. \$\endgroup\$ – isADon Aug 11 '15 at 14:20
  • \$\begingroup\$ "<remove>" only maps to single words (example: "The", "an", "a"). I get the bug you pointed out. How would I avoid this problem? \$\endgroup\$ – isADon Aug 11 '15 at 14:24
  • \$\begingroup\$ Before I answer those questions, I have a question for you: Is this practice code or production code? If it's practice code, you should be willing to "bend" the requirements and be able assume things about the input that could actually break in a real production environment. \$\endgroup\$ – RoToRa Aug 11 '15 at 14:56
  • \$\begingroup\$ I'm not sure about the exact definition of production code so let’s call it pre-production code maybe? But you are right, since the user will be able to edit the mapping file (which will be read in by the program to populate the HashMap) at his free will, it is useful to consider parts that might break the current logic of the code. \$\endgroup\$ – isADon Aug 11 '15 at 15:11
  • 1
    \$\begingroup\$ I didn't get around to post more yesterday. The reason I asked was, because for production code your problem description isn't complete enough in my opinion and I wanted to know how much work I should put in considering edge cases. However the solution of h.j.k. has covered a lot of that in the mean time. So just for completeness, here my practice code version I came up with: ideone.com/jikhRL \$\endgroup\$ – RoToRa Aug 12 '15 at 6:17

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.