Java Replacing multiple different substring in a string at once or in the most efficient way

Question

I need to replace many different sub-string in a string in the most efficient way   is there another way other then the brute force way of replacing each field using string replace

User · Answer

If you are going to be changing a String many times, then it is usually more efficient to use a StringBuilder (but measure your performance to find out):

String str = "The rain in Spain falls mainly on the plain";
StringBuilder sb = new StringBuilder(str);
// do your replacing in sb - although you'll find this trickier than simply using String
String newStr = sb.toString();

Every time you do a replace on a String, a new String object is created, because Strings are immutable. StringBuilder is mutable, that is, it can be changed as much as you want.

User · Answer

Summary  Single class implementation of Dave s answer  to automatically choose the most efficient of the two algorithms   This is a full  single class implementation based on the above excellent answer from Dave Jarvis  The class automatically chooses between the two different supplied algorithms  for maximum efficiency    This answer is for people who would just like to quickly copy and paste    ReplaceStrings class   package somepackage  import java util ArrayList  import java util Collection  import java util HashMap  import java util Map  import java util Set  import org ahocorasick trie Emit  import org ahocorasick trie Trie  import org ahocorasick trie Trie TrieBuilder  import org apache commons lang3 StringUtils          ReplaceStrings  This class is used to replace multiple strings in a section of text  with high    time efficiency  The chosen algorithms were adapted from  https   stackoverflow com a 40836618     public final class ReplaceStrings                   replace  This replaces multiple strings in a section of text  according to the supplied        search and replace definitions  For maximum efficiency  this will automatically choose        between two possible replacement algorithms                Performance note  If it is known in advance that the source text is long  then this method        signature has a very small additional performance advantage over the other method signature          Although either method signature will still choose the best algorithm               public static String replace          final String sourceText  final Map lt String  String gt  searchReplaceDefinitions            final boolean useLongAlgorithm                sourceText length    gt  1000    searchReplaceDefinitions size    gt  25           if  useLongAlgorithm                   No parameter adaptations are needed for the long algorithm              return replaceUsing AhoCorasickAlgorithm sourceText  searchReplaceDefinitions             else                  Create search and replace arrays  which are needed by the short algorithm              final ArrayList lt String gt  searchList   new ArrayList lt  gt                 final ArrayList lt String gt  replaceList   new ArrayList lt  gt                 final Set lt Map Entry lt String  String gt  gt  allEntries   searchReplaceDefinitions entrySet                for  Map Entry lt String  String gt  entry   allEntries                    searchList add entry getKey                     replaceList add entry getValue                               return replaceUsing StringUtilsAlgorithm sourceText  searchList  replaceList                                   replace  This replaces multiple strings in a section of text  according to the supplied        search strings and replacement strings  For maximum efficiency  this will automatically        choose between two possible replacement algorithms                Performance note  If it is known in advance that the source text is short  then this method        signature has a very small additional performance advantage over the other method signature          Although either method signature will still choose the best algorithm               public static String replace final String sourceText          final ArrayList lt String gt  searchList  final ArrayList lt String gt  replacementList            if  searchList size      replacementList size                  throw new RuntimeException  ReplaceStrings replace                         The search list and the replacement list must be the same size                       final boolean useLongAlgorithm    sourceText length    gt  1000    searchList size    gt  25           if  useLongAlgorithm                   Create a definitions map  which is needed by the long algorithm              HashMap lt String  String gt  definitions   new HashMap lt  gt                 final int searchListLength   searchList size                for  int index   0  index  lt  searchListLength    index                    definitions put searchList get index   replacementList get index                              return replaceUsing AhoCorasickAlgorithm sourceText  definitions             else                  No parameter adaptations are needed for the short algorithm              return replaceUsing StringUtilsAlgorithm sourceText  searchList  replacementList                                   replaceUsing StringUtilsAlgorithm  This is a string replacement algorithm that is most        efficient for sourceText under 1000 characters  and less than 25 search strings              private static String replaceUsing StringUtilsAlgorithm final String sourceText          final ArrayList lt String gt  searchList  final ArrayList lt String gt  replacementList            final String   searchArray   searchList toArray new String               final String   replacementArray   replacementList toArray new String               return StringUtils replaceEach sourceText  searchArray  replacementArray                         replaceUsing AhoCorasickAlgorithm  This is a string replacement algorithm that is most        efficient for sourceText over 1000 characters  or large lists of search strings              private static String replaceUsing AhoCorasickAlgorithm final String sourceText          final Map lt String  String gt  searchReplaceDefinitions               Create a buffer sufficiently large that re-allocations are minimized          final StringBuilder sb   new StringBuilder sourceText length    lt  lt  1           final TrieBuilder builder   Trie builder            builder onlyWholeWords            builder ignoreOverlaps            for  final String key   searchReplaceDefinitions keySet                  builder addKeyword key                     final Trie trie   builder build            final Collection lt Emit gt  emits   trie parseText sourceText           int prevIndex   0          for  final Emit emit   emits                final int matchIndex   emit getStart                 sb append sourceText substring prevIndex  matchIndex                sb append searchReplaceDefinitions get emit getKeyword                  prevIndex   emit getEnd     1                       Add the remainder of the string  contains no more matches           sb append sourceText substring prevIndex            return sb toString                          main  This contains some test and example code              public static void main String   args            String shortSource    The quick brown fox jumped over something             StringBuilder longSourceBuilder   new StringBuilder            for  int i   0  i  lt  50    i                longSourceBuilder append shortSource                     String longSource   longSourceBuilder toString            HashMap lt String  String gt  searchReplaceMap   new HashMap lt  gt             ArrayList lt String gt  searchList   new ArrayList lt  gt             ArrayList lt String gt  replaceList   new ArrayList lt  gt             searchReplaceMap put  fox    grasshopper            searchReplaceMap put  something    the mountain            searchList add  fox            replaceList add  grasshopper            searchList add  something            replaceList add  the mountain            String shortResultUsingArrays   replace shortSource  searchList  replaceList           String shortResultUsingMap   replace shortSource  searchReplaceMap           String longResultUsingArrays   replace longSource  searchList  replaceList           String longResultUsingMap   replace longSource  searchReplaceMap           System out println shortResultUsingArrays           System out println  ----------------------------------------------            System out println shortResultUsingMap           System out println  ----------------------------------------------            System out println longResultUsingArrays           System out println  ----------------------------------------------            System out println longResultUsingMap           System out println  ----------------------------------------------              Needed Maven dependencies    Add these to your pom file if needed         lt  -- Apache Commons utilities  Super commonly used utilities      https   mvnrepository com artifact org apache commons commons-lang3 -- gt       lt dependency gt           lt groupId gt org apache commons lt  groupId gt           lt artifactId gt commons-lang3 lt  artifactId gt           lt version gt 3 10 lt  version gt       lt  dependency gt        lt  -- ahocorasick  An algorithm used for efficient searching and      replacing of multiple strings      https   mvnrepository com artifact org ahocorasick ahocorasick -- gt       lt dependency gt           lt groupId gt org ahocorasick lt  groupId gt           lt artifactId gt ahocorasick lt  artifactId gt           lt version gt 0 4 0 lt  version gt       lt  dependency gt

User · Answer

How about using the replaceAll   method

User · Answer

This worked for me   String result   input replaceAll  string1 string2 string3   replacementString      Example   String input    applemangobananaarefruits   String result   input replaceAll  mango are ts   -    System out println result     Output  apple-banana-frui-

User · Answer

StringBuilder will perform replace more efficiently  since its character array buffer can be specified to a required length StringBuilder is designed for more than appending   Of course the real question is whether this is an optimisation too far   The JVM is very good at handling creation of multiple objects and the subsequent garbage collection  and like all optimisation questions  my first question is whether you ve measured this and determined that it s a problem

User · Answer

If the string you are operating on is very long  or you are operating on many strings  then it could be worthwhile using a java util regex Matcher  this requires time up-front to compile  so it won t be efficient if your input is very small or your search pattern changes frequently    Below is a full example  based on a list of tokens taken from a map   Uses StringUtils from Apache Commons Lang    Map lt String String gt  tokens   new HashMap lt String String gt     tokens put  cat    Garfield    tokens put  beverage    coffee     String template     cat  really needs some  beverage         Create pattern of the format    cat beverage    String patternString          StringUtils join tokens keySet                 Pattern pattern   Pattern compile patternString   Matcher matcher   pattern matcher template    StringBuffer sb   new StringBuffer    while matcher find          matcher appendReplacement sb  tokens get matcher group 1       matcher appendTail sb    System out println sb toString       Once the regular expression is compiled  scanning the input string is generally very quick  although if your regular expression is complex or involves backtracking then you would still need to benchmark in order to confirm this

User · Answer

Check this   String format str STR      For instance   String format   Put your  s where your  s is    money    mouth

User · Answer

Rythm a java template engine now released with an new feature called String interpolation mode which allows you do something like   String result   Rythm render   name is inviting you    Diana      The above case shows you can pass argument to template by position  Rythm also allows you to pass arguments by name   Map lt String  Object gt  args   new HashMap lt String  Object gt     args put  title    Mr     args put  name    John    String result   Rythm render  Hello  title  name   args     Note Rythm is VERY FAST  about 2 to 3 times faster than String format and velocity  because it compiles the template into java byte code  the runtime performance is very close to concatentation with StringBuilder   Links    Check the full featured demonstration read a brief introduction to Rythm  download the latest package or  fork it

User · Answer

The below is based on Todd Owen s answer  That solution has the problem that if the replacements contain characters that have special meaning in regular expressions  you can get unexpected results  I also wanted to be able to optionally do a case-insensitive search  Here is what I came up with          Performs simultaneous search replace of multiple strings  Case Sensitive      public String replaceMultiple String target  Map lt String  String gt  replacements      return replaceMultiple target  replacements  true             Performs simultaneous search replace of multiple strings          param target        string to perform replacements on      param replacements  map where key represents value to search for  and value represents replacem     param caseSensitive whether or not the search is case-sensitive      return replaced string     public String replaceMultiple String target  Map lt String  String gt  replacements  boolean caseSensitive      if target    null       equals target     replacements    null    replacements size      0      return target       if we are doing case-insensitive replacements  we need to make the map case-insensitive--make a new map with all-lower-case keys   if  caseSensitive        Map lt String  String gt  altReplacements   new HashMap lt String  String gt  replacements size         for String key   replacements keySet          altReplacements put key toLowerCase    replacements get key         replacements   altReplacements         StringBuilder patternString   new StringBuilder      if  caseSensitive      patternString append    i        patternString append         boolean first   true    for String key   replacements keySet          if first        first   false      else       patternString append            patternString append Pattern quote key          patternString append          Pattern pattern   Pattern compile patternString toString       Matcher matcher   pattern matcher target      StringBuffer res   new StringBuffer      while matcher find          String match   matcher group 1       if  caseSensitive        match   match toLowerCase        matcher appendReplacement res  replacements get match          matcher appendTail res      return res toString        Here are my unit test cases    Test public void replaceMultipleTest       assertNull ExtStringUtils replaceMultiple null  null      assertNull ExtStringUtils replaceMultiple null  Collections  lt String  String gt emptyMap        assertEquals     ExtStringUtils replaceMultiple     null      assertEquals     ExtStringUtils replaceMultiple     Collections  lt String  String gt emptyMap         assertEquals  folks  we are not sane anymore  with me  i promise you  we will burn in flames   ExtStringUtils replaceMultiple  folks  we are not winning anymore  with me  i promise you  we will win big league   makeMap  win big league    burn in flames    winning    sane         assertEquals  bcaacbbcaacb   ExtStringUtils replaceMultiple  abccbaabccba   makeMap  a    b    b    c    c    a        assertEquals  bcaCBAbcCCBb   ExtStringUtils replaceMultiple  abcCBAabCCBa   makeMap  a    b    b    c    c    a        assertEquals  bcaacbbcaacb   ExtStringUtils replaceMultiple  abcCBAabCCBa   makeMap  a    b    b    c    c    a    false       assertEquals  c colon  backslash temp backslash  star  dot  star    ExtStringUtils replaceMultiple  c   temp        makeMap        dot           colon            backslash           star     false       private Map lt String  String gt  makeMap String     vals      Map lt String  String gt  map   new HashMap lt String  String gt  vals length   2     for int i   1  i  lt  vals length  i   2      map put vals i-1   vals i      return map

User · Answer

Algorithm  One of the most efficient ways to replace matching strings  without regular expressions  is to use the Aho-Corasick algorithm with a performant Trie  pronounced  try    fast hashing algorithm  and efficient collections implementation   Simple Code  A simple solution leverages Apache s StringUtils replaceEach as follows     private String testStringUtils      final String text  final Map lt String  String gt  definitions         final String   keys   keys  definitions        final String   values   values  definitions         return StringUtils replaceEach  text  keys  values          This slows down on large texts   Fast Code  Bor s implementation of the Aho-Corasick algorithm introduces a bit more complexity that becomes an implementation detail by using a fa  ade with the same method signature     private String testBorAhoCorasick      final String text  final Map lt String  String gt  definitions            Create a buffer sufficiently large that re-allocations are minimized      final StringBuilder sb   new StringBuilder  text length    lt  lt  1         final TrieBuilder builder   Trie builder        builder onlyWholeWords        builder removeOverlaps         final String   keys   keys  definitions         for  final String key   keys           builder addKeyword  key               final Trie trie   builder build        final Collection lt Emit gt  emits   trie parseText  text         int prevIndex   0       for  final Emit emit   emits           final int matchIndex   emit getStart           sb append  text substring  prevIndex  matchIndex            sb append  definitions get  emit getKeyword              prevIndex   emit getEnd     1                Add the remainder of the string  contains no more matches       sb append  text substring  prevIndex           return sb toString          Benchmarks  For the benchmarks  the buffer was created using randomNumeric as follows     private final static int TEXT SIZE   1000    private final static int MATCHES DIVISOR   10     private final static StringBuilder SOURCE       new StringBuilder  randomNumeric  TEXT SIZE        Where MATCHES DIVISOR dictates the number of variables to inject     private void injectVariables  final Map lt String  String gt  definitions         for  int i    SOURCE length     MATCHES DIVISOR    1  i  gt  0  i--           final int r   current   nextInt  1  SOURCE length            SOURCE insert  r  randomKey  definitions                  The benchmark code itself  JMH seemed overkill    long duration   System nanoTime    final String result   testBorAhoCorasick  text  definitions    duration   System nanoTime   - duration  System out println  elapsed  duration        1 000 000   1 000  A simple micro-benchmark with 1 000 000 characters and 1 000 randomly-placed strings to replace    testStringUtils  25 seconds  25533 millis testBorAhoCorasick  0 seconds  68 millis   No contest   10 000   1 000  Using 10 000 characters and 1 000 matching strings to replace    testStringUtils  1 seconds  1402 millis testBorAhoCorasick  0 seconds  37 millis   The divide closes   1 000   10  Using 1 000 characters and 10 matching strings to replace    testStringUtils  0 seconds  7 millis testBorAhoCorasick  0 seconds  19 millis   For short strings  the overhead of setting up Aho-Corasick eclipses the brute-force approach by StringUtils replaceEach   A hybrid approach based on text length is possible  to get the best of both implementations   Implementations  Consider comparing other implementations for text longer than 1 MB  including    https   github com RokLenarcic AhoCorasick https   github com hankcs AhoCorasickDoubleArrayTrie https   github com raymanrt aho-corasick https   github com ssundaresan Aho-Corasick https   github com jmhsieh aho-corasick https   github com quest-oss Mensa   Papers  Papers and information relating to the algorithm    http   www cs uku fi research publications reports A-2005-2 pdf https   pdfs semanticscholar org 3547 ac839d02f6efe3f6f76a8289738a22528442 pdf http   www ece ncsu edu asic ece792A 2009 ECE792A Readings files 00989753 pdf http   blog ivank net aho-corasick-algorithm-in-as3 html

User · Answer

public String replace String input  Map lt String  String gt  pairs         Reverse lexic-order of keys is good enough for most cases       as it puts longer words before their prefixes   tool  before  too         However  there are corner cases  which this algorithm doesn t handle      no matter what order of keys you choose  eg  it fails to match  edit       before  bed  in    bedit    because  bed  appears first in the input       but  edit  may be the desired longer match  Depends which you prefer    final Map lt String  String gt  sorted          new TreeMap lt String  String gt  Collections reverseOrder       sorted putAll pairs     final String   keys   sorted keySet   toArray new String sorted size        final String   vals   sorted values   toArray new String sorted size        final int lo   0  hi   input length      final StringBuilder result   new StringBuilder      int s   lo    for  int i   s  i  lt  hi  i          for  int p   0  p  lt  keys length  p            if  input regionMatches i  keys p   0  keys p  length                  TODO  check for  edit   if this is  bed  in    bedit    case             i e  look ahead for all prioritized longer keys starting within            the current match region  iff found  then ignore match   bed              and continue search  find  edit  later   else handle match                if  better-match-overlaps-right-ahead               continue          result append input  s  i  append vals p            i    keys p  length            s   i--                      if  s    lo     no matches  no changes      return input    return result append input  s  hi  toString

[java] Java Replacing multiple different substring in a string at once (or in the most efficient way)

Examples related to java

Examples related to string

Examples related to replace