반응형
Java 한 문자열에서 여러 개의 서로 다른 서브스트링을 동시에 치환(또는 가장 효율적인 방법으로)
문자열 내의 많은 다른 서브스트링을 가장 효율적인 방법으로 치환해야 합니다.스트링을 사용하여 각 필드를 치환하는 broute force 방법 외에 다른 방법이 있습니까?replace?
동작하는 문자열이 매우 길거나 다수의 문자열로 동작하는 경우 java.util.regex를 사용하는 것이 좋습니다.Matcher(컴파일 전에 시간이 필요하기 때문에 입력이 매우 적거나 검색 패턴이 자주 바뀌면 효율적이지 않습니다.)
다음은 지도에서 가져온 토큰 목록을 기반으로 한 전체 예입니다(Apache Commons Lang의 String Utils 사용).
Map<String,String> tokens = new HashMap<String,String>();
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());
정규 표현이 컴파일되면 입력 문자열 스캔은 일반적으로 매우 빠릅니다(단, 정규 표현이 복잡하거나 역추적을 수반하는 경우에는 이를 확인하기 위해 벤치마크가 필요합니다).
알고리즘.
일치하는 문자열(정규 표현 없음)을 대체하는 가장 효율적인 방법 중 하나는 Aho-Corasick 알고리즘을 퍼포먼스 Trie('try'로 발음), 고속 해시 알고리즘 및 효율적인 수집 구현과 함께 사용하는 것입니다.
심플 코드
Apache를 활용하는 간단한 솔루션은 다음과 같습니다.
private String testStringUtils(
final String text, final Map<String, String> definitions ) {
final String[] keys = keys( definitions );
final String[] values = values( definitions );
return StringUtils.replaceEach( text, keys, values );
}
큰 텍스트에서는 속도가 느려집니다.
퍼스트 코드
Bor의 Aho-Corasick 알고리즘 실장은 조금 더 복잡해졌습니다.이것은 같은 메서드 시그니처의 파사드를 사용함으로써 구현의 상세 내용이 됩니다.
private String testBorAhoCorasick(
final String text, final Map<String, String> definitions ) {
// Create a buffer sufficiently large that re-allocations are minimized.
final StringBuilder sb = new StringBuilder( text.length() << 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<Emit> 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();
}
벤치마크
벤치마크에서는 다음과 같이 randomNumeric을 사용하여 버퍼가 작성되었습니다.
private final static int TEXT_SIZE = 1000;
private final static int MATCHES_DIVISOR = 10;
private final static StringBuilder SOURCE
= new StringBuilder( randomNumeric( TEXT_SIZE ) );
어디 어디에MATCHES_DIVISOR변수의 수를 주입해:A주입할 변수의수를 지정합니다 Dictates.
private void injectVariables( final Map<String, String> definitions ) {
for( int i = (SOURCE.length() / MATCHES_DIVISOR) + 1; i > 0; i-- ) {
final int r = current().nextInt( 1, SOURCE.length() );
SOURCE.insert( r, randomKey( definitions ) );
}
}
벤치마크 코드 자체(JMH가 과잉으로 생각됨):
long duration = System.nanoTime();
final String result = testBorAhoCorasick( text, definitions );
duration = System.nanoTime() - duration;
System.out.println( elapsed( duration ) );
1,000,000 : 1,000
1,000,000자의 문자와 1,000개의 문자열을 임의로 배치하여 치환하는 단순한 마이크로벤치마크
- testStringUtils: 25초, 25533밀리
- testBorAhoCorasick: 0초, 68밀리
경합은 없습니다.
10,000 : 1,000
10,000자 및 1,000개의 일치하는 문자열을 사용하여 대체:
- testStringUtils: 1초, 1402밀리
- testBorAhoCorasick: 0초, 37밀리
칸막이가 닫힙니다.
1,000 : 10
1,000자 및 10개의 일치하는 문자열을 사용하여 대체:
- test String Utils: 0초, 7밀리
- testBorAhoCorasick: 0초, 19밀리초
짧은 문자열 내용은 Aho-Corasick을 설정하는 오버 헤드짧은 문자열의 경우, Aho-Corasick 설치의 오버헤드는 다음과 같은 강력한 접근 방식을 능가합니다가 주먹 구구 추구 방식을 가린다.StringUtils.replaceEach..
텍스트 길이에 기초한 하이브리드 접근방식은 두 구현의 장점을 최대한 활용하기 위해 가능합니다.
실장
1MB를 초과하는 텍스트에 대해 다음을 포함하여 다른 구현을 비교하는 것을 고려해 보십시오.
- 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
페이퍼
알고리즘에 관한 문서 및 정보:
- 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
이 방법은 효과가 있었습니다.
String result = input.replaceAll("string1|string2|string3","replacementString");
예제:
String input = "applemangobananaarefruits";
String result = input.replaceAll("mango|are|ts","-");
System.out.println(result);
출력: 애플바나나-후라이-
String을 여러 번 변경할 경우 String Builder를 사용하는 것이 일반적으로 더 효율적입니다(단, 성능을 측정하여 확인할 수 있습니다.
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();
String에서 치환을 수행할 때마다 String 객체가 새로 생성됩니다.String은 불변하기 때문입니다.String Builder는 변경할 수 있습니다.즉, 원하는 만큼 변경할 수 있습니다.
StringBuilder이후 문자 배열 버퍼는 필요한 길이로 지정될 수 있는 더 효율적으로를 교체하는 것을 수행할 것이다.는 문자 배열 버퍼를 필요한 길이로 지정할 수 있기 때문에 치환을 보다 효율적으로 수행합니다.StringBuilder추가하는 이상을 위한 것입니다!추가이상의 용도로 설계되었습니다.
물론 진짜 질문은 이것이 너무 지나친 최적화인가 하는 것이다.JVM은 여러 개체의 생성과 그에 따른 가비지 수집을 매우 잘 처리합니다. 모든 최적화 질문과 마찬가지로 첫 번째 질문은 이 값을 측정하여 문제가 있다고 판단했는지 여부입니다.
체크해 주세요.
String.format(str,STR[])
예:
String.format( "Put your %s where your %s is", "money", "mouth" );
Rythm Java 템플릿엔진은 String interpolation mode라고 불리는 새로운 기능과 함께 출시되어 다음과 같은 작업을 수행할 수 있습니다.
String result = Rythm.render("@name is inviting you", "Diana");
위의 예에서는 위치를 기준으로 템플릿에 인수를 전달할 수 있음을 보여 줍니다.Rythm에서는 다음 이름으로 인수를 전달할 수도 있습니다.
Map<String, Object> args = new HashMap<String, Object>();
args.put("title", "Mr.");
args.put("name", "John");
String result = Rythm.render("Hello @title @name", args);
주의: Rythm은 String보다 약 2~3배 빠른 매우 빠른 속도입니다.템플릿이 Java 바이트 코드로 컴파일되기 때문에 실행 시 퍼포먼스는 String Builder와의 콘텐션에 매우 가깝습니다.
링크:
- 전체 데모를 확인합니다.
- Rythm에 대한 간단한 소개를 읽다
- 최신 패키지 다운로드 또는
- 갈림길에 서다
아래는 Todd Owen의 답변을 바탕으로 한 것입니다.이 솔루션에는 정규 표현에 특별한 의미를 가진 문자가 치환되어 있는 경우 예기치 않은 결과가 발생할 수 있다는 문제가 있습니다.대소문자를 구분하지 않는 검색도 옵션으로 하고 싶었습니다.제가 생각해낸 것은 다음과 같습니다.
/**
* Performs simultaneous search/replace of multiple strings. Case Sensitive!
*/
public String replaceMultiple(String target, Map<String, String> 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<String, String> 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<String, String> altReplacements = new HashMap<String, String>(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();
}
유닛 테스트 케이스는 다음과 같습니다.
@Test
public void replaceMultipleTest() {
assertNull(ExtStringUtils.replaceMultiple(null, null));
assertNull(ExtStringUtils.replaceMultiple(null, Collections.<String, String>emptyMap()));
assertEquals("", ExtStringUtils.replaceMultiple("", null));
assertEquals("", ExtStringUtils.replaceMultiple("", Collections.<String, String>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<String, String> makeMap(String ... vals) {
Map<String, String> map = new HashMap<String, String>(vals.length / 2);
for(int i = 1; i < vals.length; i+= 2)
map.put(vals[i-1], vals[i]);
return map;
}
replaceAll() 메서드를 사용하는 것은 어떻습니까?
public String replace(String input, Map<String, String> 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<String, String> sorted =
new TreeMap<String, String>(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 < hi; i++) {
for (int p = 0; p < 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();
}
요약: Dave의 답변을 단일 클래스에서 구현하여 두 알고리즘 중 가장 효율적인 알고리즘을 자동으로 선택합니다.
이는 Dave Jarvis의 상기 훌륭한 답변을 바탕으로 한 완전한 단일 클래스 구현입니다.이 클래스는 효율을 최대화하기 위해 제공된 두 가지 알고리즘 중 하나를 자동으로 선택합니다(이 답변은 빠르게 복사하여 붙여넣기를 원하는 사용자를 위한 것입니다).
ReplaceStrings 클래스:
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<String, String> searchReplaceDefinitions) {
final boolean useLongAlgorithm
= (sourceText.length() > 1000 || searchReplaceDefinitions.size() > 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<String> searchList = new ArrayList<>();
final ArrayList<String> replaceList = new ArrayList<>();
final Set<Map.Entry<String, String>> allEntries = searchReplaceDefinitions.entrySet();
for (Map.Entry<String, String> 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<String> searchList, final ArrayList<String> 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() > 1000 || searchList.size() > 25);
if (useLongAlgorithm) {
// Create a definitions map, which is needed by the long algorithm.
HashMap<String, String> definitions = new HashMap<>();
final int searchListLength = searchList.size();
for (int index = 0; index < 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<String> searchList, final ArrayList<String> 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<String, String> searchReplaceDefinitions) {
// Create a buffer sufficiently large that re-allocations are minimized.
final StringBuilder sb = new StringBuilder(sourceText.length() << 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<Emit> 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 < 50; ++i) {
longSourceBuilder.append(shortSource);
}
String longSource = longSourceBuilder.toString();
HashMap<String, String> searchReplaceMap = new HashMap<>();
ArrayList<String> searchList = new ArrayList<>();
ArrayList<String> replaceList = new ArrayList<>();
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("----------------------------------------------");
}
}
필요한 메이븐 의존관계:
(필요한 경우 POM 파일에 추가합니다.)
<!-- Apache Commons utilities. Super commonly used utilities.
https://mvnrepository.com/artifact/org.apache.commons/commons-lang3 -->
<dependency>
<groupId>org.apache.commons</groupId>
<artifactId>commons-lang3</artifactId>
<version>3.10</version>
</dependency>
<!-- ahocorasick, An algorithm used for efficient searching and
replacing of multiple strings.
https://mvnrepository.com/artifact/org.ahocorasick/ahocorasick -->
<dependency>
<groupId>org.ahocorasick</groupId>
<artifactId>ahocorasick</artifactId>
<version>0.4.0</version>
</dependency>
언급URL : https://stackoverflow.com/questions/1326682/java-replacing-multiple-different-substring-in-a-string-at-once-or-in-the-most
반응형
'programing' 카테고리의 다른 글
| 스프링 부트 내장 HornetQ 클러스터가 메시지를 전달하지 않음 (0) | 2022.09.04 |
|---|---|
| SHOW PROCESS LIST에서 전체 쿼리를 표시하는 방법 (0) | 2022.09.04 |
| 봄철 @Component, @Repository 및 @Service 주석의 차이점은 무엇입니까? (0) | 2022.09.01 |
| Vuex 액션 내의 Axios 함수에서 디스패치 캐치(오류)로 오류 메시지를 반환하려면 어떻게 해야 합니까? (0) | 2022.09.01 |
| typescript와 함께 mapState 사용 (0) | 2022.09.01 |