Câu hỏi Java Thay thế nhiều chuỗi con khác nhau trong một chuỗi cùng một lúc (hoặc theo cách hiệu quả nhất)


Tôi cần phải thay thế nhiều chuỗi con khác nhau trong một chuỗi theo cách hiệu quả nhất. là có một cách khác sau đó cách bạo lực của thay thế từng lĩnh vực bằng cách sử dụng string.replace?


76
2017-08-25 07:52


gốc




Các câu trả lời:


Nếu chuỗi bạn đang hoạt động là rất dài, hoặc bạn đang hoạt động trên nhiều chuỗi, thì nó có thể đáng giá bằng cách sử dụng một java.util.regex.Matcher (điều này đòi hỏi thời gian lên phía trước để biên dịch, vì vậy nó sẽ không hiệu quả nếu đầu vào của bạn rất nhỏ hoặc mẫu tìm kiếm của bạn thay đổi thường xuyên).

Dưới đây là ví dụ đầy đủ, dựa trên danh sách các thẻ được lấy từ bản đồ. (Sử dụng StringUtils từ Apache Commons Lang).

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

Khi biểu thức chính quy được biên dịch, việc quét chuỗi đầu vào thường rất nhanh (mặc dù cụm từ thông dụng của bạn phức tạp hoặc liên quan đến việc quay ngược lại, bạn vẫn sẽ cần điểm chuẩn để xác nhận điều này!)


84
2017-08-25 08:55



Có, cần phải được đo điểm chuẩn cho số lần lặp lại. - techzen
Tôi nghĩ bạn nên thoát khỏi các ký tự đặc biệt trong mỗi mã thông báo trước khi thực hiện "%(" + StringUtils.join(tokens.keySet(), "|") + ")%"; - Willmore
Lưu ý rằng người ta có thể sử dụng StringBuilder cho tốc độ cao hơn một chút. StringBuilder không được đồng bộ hóa. chỉnh sửa Rất tiếc, chỉ hoạt động với java 9 - Tinus Tate


Thuật toán

Một trong những cách hiệu quả nhất để thay thế các chuỗi phù hợp (không có cụm từ thông dụng) là sử dụng Thuật toán Aho-Corasick với một người biểu diễn Trie (phát âm là "thử"), nhanh băm thuật toán và hiệu quả bộ sưu tập thực hiện.

Mã đơn giản

Có lẽ mã đơn giản nhất để viết đòn bẩy của Apache StringUtils.replaceEach như sau:

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

Điều này làm chậm các văn bản lớn.

Mã nhanh

Thực hiện của Bor của thuật toán Aho-Corasick giới thiệu một chút phức tạp hơn mà trở thành một chi tiết thực hiện bằng cách sử dụng một façade với cùng một chữ ký phương thức:

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

Điểm chuẩn

Đối với các tiêu chí chuẩn, bộ đệm được tạo bằng cách sử dụng randomNumeric như sau:

  private final static int TEXT_SIZE = 1000;
  private final static int MATCHES_DIVISOR = 10;

  private final static StringBuilder SOURCE
    = new StringBuilder( randomNumeric( TEXT_SIZE ) );

Ở đâu MATCHES_DIVISOR quy định số lượng biến cần tiêm:

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

Bản thân mã điểm chuẩn (JMH dường như quá mức cần thiết):

long duration = System.nanoTime();
final String result = testBorAhoCorasick( text, definitions );
duration = System.nanoTime() - duration;
System.out.println( elapsed( duration ) );

1.000.000: 1.000

Một điểm chuẩn vi mô đơn giản với 1.000.000 ký tự và 1.000 chuỗi được đặt ngẫu nhiên để thay thế.

  • testStringUtils: 25 giây, 25533 millis
  • testBorAhoCorasick: 0 giây, 68 millis

Không có cuộc thi.

10.000: 1.000

Sử dụng 10.000 ký tự và 1.000 chuỗi phù hợp để thay thế:

  • testStringUtils: 1 giây, 1402 millis
  • testBorAhoCorasick: 0 giây, 37 millis

Sự phân chia đóng lại.

1.000: 10

Sử dụng 1.000 ký tự và 10 chuỗi phù hợp để thay thế:

  • testStringUtils: 0 giây, 7 millis
  • testBorAhoCorasick: 0 giây, 19 millis

Đối với các chuỗi ngắn, chi phí thiết lập Aho-Corasick làm lu mờ cách tiếp cận vũ phu StringUtils.replaceEach.

Một phương pháp lai dựa trên độ dài văn bản là có thể, để có được tốt nhất của cả hai triển khai.

Triển khai

Cân nhắc so sánh các triển khai khác cho văn bản dài hơn 1 MB, bao gồm:

Giấy tờ

Các giấy tờ và thông tin liên quan đến thuật toán:


33
2017-11-28 03:08



Kudos cho việc cập nhật câu hỏi này với thông tin giá trị mới, điều đó rất hay. Tôi nghĩ rằng một tiêu chuẩn JMH vẫn còn phù hợp, ít nhất là cho các giá trị hợp lý như 10.000: 1.000 và 1,000: 10 (JIT có thể làm tối ưu hóa phép thuật đôi khi). - Tunaki


Nếu bạn sẽ thay đổi một chuỗi nhiều lần, thì thường thì hiệu quả hơn khi sử dụng một StringBuilder (nhưng đo lường hiệu suất của bạn để tìm hiểu):

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

Mỗi khi bạn thực hiện một thay thế trên một String, một đối tượng String mới được tạo ra, bởi vì các chuỗi là không thay đổi. StringBuilder có thể thay đổi, có nghĩa là, nó có thể được thay đổi nhiều như bạn muốn.


7
2017-08-25 08:01





StringBuilder sẽ thực hiện thay thế hiệu quả hơn, vì bộ đệm mảng ký tự của nó có thể được xác định theo độ dài yêu cầu.StringBuilder được thiết kế để thêm nhiều hơn nữa!

Tất nhiên câu hỏi thực sự là liệu đây có phải là một sự tối ưu hóa quá xa? JVM rất giỏi trong việc xử lý việc tạo nhiều đối tượng và thu gom rác tiếp theo, và giống như tất cả các câu hỏi tối ưu hóa, câu hỏi đầu tiên của tôi là liệu bạn đã đo được điều này và xác định rằng đó là một vấn đề.


4
2017-08-25 08:02





Cách sử dụng thay thế tất cả() phương pháp?


3
2017-08-25 07:59



OP cho biết "nhiều chuỗi con khác nhau" - Steve McLeod
Nhiều nền tảng khác nhau có thể được xử lý trong một regex (/substring1|substring2|.../). Tất cả phụ thuộc vào loại thay thế mà OP đang cố gắng làm. - Avi
OP đang tìm kiếm thứ gì đó hiệu quả hơn str.replaceAll(search1, replace1).replaceAll(search2, replace2).replaceAll(search3, replace3).replaceAll(search4, replace4) - Kip


Kiểm tra điều này:

String.format (str, STR [])

...

Ví dụ:

String.format ("Đặt% s của bạn ở nơi% s của bạn là", "tiền", "miệng");


2
2017-12-30 08:16





Rythm một công cụ tạo mẫu java bây giờ được phát hành với một tính năng mới được gọi là Chế độ nội suy chuỗi cho phép bạn làm điều gì đó như:

String result = Rythm.render("@name is inviting you", "Diana");

Trường hợp trên cho thấy bạn có thể chuyển đối số cho mẫu theo vị trí. Nhịp điệu cũng cho phép bạn chuyển đối số theo tên:

Map<String, Object> args = new HashMap<String, Object>();
args.put("title", "Mr.");
args.put("name", "John");
String result = Rythm.render("Hello @title @name", args);

Lưu ý Rythm là VERY FAST, nhanh gấp 2 đến 3 lần so với String.format và vận tốc, bởi vì nó biên dịch khuôn mẫu thành mã byte java, hiệu suất thời gian chạy rất gần với sự nối kết với StringBuilder.

Liên kết:


2
2017-07-01 08:42



Đây là khả năng rất rất cũ có sẵn với nhiều ngôn ngữ templating như vận tốc, JSP thậm chí. Ngoài ra, nó không trả lời câu hỏi không yêu cầu các chuỗi tìm kiếm ở định dạng được xác định trước. - Angsuman Chakraborty
Thú vị, câu trả lời được chấp nhận cung cấp một ví dụ: "%cat% really needs some %beverage%."; không phải vậy % mã thông báo được phân tách bằng định dạng được xác định trước? Điểm đầu tiên của bạn thậm chí còn hài hước hơn, JDK cung cấp rất nhiều "khả năng cũ", một số trong số đó bắt đầu từ những năm 90, tại sao mọi người lại sử dụng chúng? Ý kiến ​​của bạn và downvoting không thực hiện bất kỳ ý nghĩa thực sự - Gelin Luo
Điểm giới thiệu động cơ mẫu Rythm khi đã có nhiều công cụ mẫu có sẵn và được sử dụng rộng rãi như Velocity hoặc Freemarker để khởi động là gì? Ngoài ra, tại sao lại giới thiệu một sản phẩm khác khi các chức năng cốt lõi của Java là đủ. Tôi thực sự nghi ngờ tuyên bố của bạn về hiệu suất vì Pattern cũng có thể được biên dịch. Rất thích nhìn thấy một số số thực. - Angsuman Chakraborty
Màu xanh lá cây, Bạn đang thiếu điểm. Người hỏi muốn thay thế các chuỗi tùy ý trong khi giải pháp của bạn sẽ chỉ thay thế các chuỗi ở định dạng được xác định trước như @ đi trước. Có, ví dụ sử dụng% nhưng chỉ là một ví dụ, không phải là một yếu tố hạn chế. Vì vậy, bạn trả lời không trả lời câu hỏi và do đó là điểm tiêu cực. - Angsuman Chakraborty


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

0
2017-08-03 08:35





Dưới đây là dựa trên Câu trả lời của Todd Owen. Giải pháp đó có vấn đề là nếu các thay thế chứa các ký tự có ý nghĩa đặc biệt trong các biểu thức chính quy, bạn có thể nhận được các kết quả không mong muốn. Tôi cũng muốn có thể tùy ý thực hiện tìm kiếm phân biệt chữ hoa chữ thường. Đây là những gì tôi đã đưa ra:

/**
 * 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();
}

Dưới đây là các trường hợp thử nghiệm đơn vị của tôi:

@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;
}

0
2017-10-05 15:42