Альтернатива последовательной String.replace

Ответ 1

Хотя StringBuilder.replace() является большим улучшением по сравнению с String.replace(), он все еще очень далек от оптимального.

Проблема с StringBuilder.replace() заключается в том, что если замена имеет разную длину, чем сменная часть (применима к нашему случаю), может потребоваться выделить более крупный внутренний массив char, и содержимое должно быть скопировано, и то произойдет замена (что также связано с копированием).

Представьте себе: у вас есть текст с 10.000 символами. Если вы хотите заменить подстроку "XY", найденную в позиции 1 (2-й символ), на "ABC", реализация должна перераспределить буфер char, который по крайней мере больше на 1, должен скопировать старый контент в новый массив, и он должен скопировать 9,997 символов (начиная с позиции 3) справа на 1, чтобы поместить "ABC" в место "XY", и, наконец, символы "ABC" будут скопированы в положение стартера 1. Это нужно сделать для каждой замены! Это медленно.

Более быстрое решение: создание выхода на лету

Мы можем создавать выходные данные "на лету": части, которые не содержат заменяемых текстов, могут просто быть добавлены к выходу, и если мы найдем заменяемый фрагмент, вместо него добавим замену. Теоретически это достаточно, чтобы петля над входом только один раз для генерации вывода. Звучит просто, и это не так сложно реализовать.

Реализация:

Мы будем использовать предустановку Map с отображениями заменяемых заменяющих строк:

Map<String, String> map = new HashMap<>();
map.put("<h1>", "<big><big><big><b>");
map.put("</h1>", "</b></big></big></big>");
map.put("<h2>", "<big><big>");
map.put("</h2>", "</big></big>");
map.put("<h3>", "<big>");
map.put("</h3>", "</big>");
map.put("<h4>", "<b>");
map.put("</h4>", "</b>");
map.put("<h5>", "<small><b>");
map.put("</h5>", "</b></small>");
map.put("<h6>", "<small>");
map.put("</h6>", "</small>");

И используя это, вот код замены: (больше объяснений после кода)

public static String replaceTags(String src, Map<String, String> map) {
    StringBuilder sb = new StringBuilder(src.length() + src.length() / 2);

    for (int pos = 0;;) {
        int ltIdx = src.indexOf('<', pos);
        if (ltIdx < 0) {
            // No more '<', we're done:
            sb.append(src, pos, src.length());
            return sb.toString();
        }

        sb.append(src, pos, ltIdx); // Copy chars before '<'
        // Check if our hit is replaceable:
        boolean mismatch = true;
        for (Entry<String, String> e : map.entrySet()) {
            String key = e.getKey();
            if (src.regionMatches(ltIdx, key, 0, key.length())) {
                // Match, append the replacement:
                sb.append(e.getValue());
                pos = ltIdx + key.length();
                mismatch = false;
                break;
            }
        }
        if (mismatch) {
            sb.append('<');
            pos = ltIdx + 1;
        }
    }
}

Тестирование:

String in = "Yo<h1>TITLE</h1><h3>Hi!</h3>Nice day.<h6>Hi back!</h6>End";
System.out.println(in);
System.out.println(replaceTags(in, map));

Выход: (завернутый, чтобы избежать полосы прокрутки)

Yo<h1>TITLE</h1><h3>Hi!</h3>Nice day.<h6>Hi back!</h6>End

Yo<big><big><big><b>TITLE</b></big></big></big><big>Hi!</big>Nice day.
<small>Hi back!</small>End

Это решение быстрее, чем использование регулярных выражений, так как это связано со значительными издержками, такими как компиляция a Pattern, создание Matcher и т.д., а регулярное выражение также намного более общее. Он также создает много временных объектов под капотом, которые выбрасываются после замены. Здесь я использую только массив StringBuilder (плюс char под его капотом), и код выполняет итерацию по вводу String только один раз. Кроме того, это решение намного быстрее, используя StringBuilder.replace(), как описано в верхней части этого ответа.

Примечания и пояснения

Я инициализировал StringBuilder в методе replaceTags() следующим образом:

StringBuilder sb = new StringBuilder(src.length() + src.length() / 2);

Итак, в основном я создал его с начальной мощностью 150% от длины оригинала String. Это связано с тем, что наши замены длиннее, чем сменные тексты, поэтому, если происходит замена, выход, очевидно, будет длиннее, чем вход. Предоставление большей начальной емкости StringBuilder не приведет к внутреннему перераспределению char[] (конечно, требуемая начальная емкость зависит от пар заменяемых замен и их частоты/вхождения на входе, но это + 50% является хорошая верхняя оценка).

Я также использовал тот факт, что все сменные строки начинаются с символа '<', поэтому поиск следующего потенциального сменного положения становится быстрым:

int ltIdx = src.indexOf('<', pos);

Это просто простой цикл и char сравнения внутри String, и поскольку он всегда начинает поиск с pos (а не с начала ввода), общий код выполняет итерацию только на вход String один раз.

И, наконец, чтобы определить, существует ли сменный String в потенциальной позиции, мы используем метод String.regionMatches() для проверки сменных укусы, которые также пылают, как все, что он делает, просто сравнивают значения char в цикле и возвращаются с самым первым несоответствующим символом.

И ПЛЮС:

Вопрос не упоминает об этом, но наш вход - это HTML-документ. HTML-теги нечувствительны к регистру, что означает, что вход может содержать <H1> вместо <H1>.
Для этого алгоритма это не проблема. regionMatches() в классе String имеет перегрузку, которая поддерживает нечувствительность к регистру:

boolean regionMatches(boolean ignoreCase, int toffset, String other,
                          int ooffset, int len);

Итак, если мы хотим изменить наш алгоритм, чтобы также найти и заменить теги ввода одинаковыми, но они написаны с использованием различного случая с буквой, все, что нам нужно изменить, это одна строка:

if (src.regionMatches(true, ltIdx, key, 0, key.length())) {

Используя этот модифицированный код, сменные теги становятся нечувствительными к регистру:

Yo<H1>TITLE</H1><h3>Hi!</h3>Nice day.<H6>Hi back!</H6>End
Yo<big><big><big><b>TITLE</b></big></big></big><big>Hi!</big>Nice day.
<small>Hi back!</small>End

Ответ 2

Для производительности - используйте StringBuilder. Для удобства вы можете использовать Map для хранения значений и замен.

Map<String, String> map = new HashMap<>();
map.put("<h1>","<big><big><big><b>");
map.put("</h1>","</b></big></big></big>");
map.put("<h2>","<big><big>");
...
StringBuilder builder = new StringBuilder(yourString);
for (String key : map.keySet()) {
    replaceAll(builder, key, map.get(key));
}

... Чтобы заменить все вхождения в StringBuilder, вы можете проверить здесь: Заменить все вхождения строки с помощью StringBuilder?

public static void replaceAll(StringBuilder builder, String from, String to)
{
    int index = builder.indexOf(from);
    while (index != -1)
    {
        builder.replace(index, index + from.length(), to);
        index += to.length(); // Move to the end of the replacement
        index = builder.indexOf(from, index);
    }
}

Ответ 3

К сожалению, StringBuilder не предоставляет метод replace(string,string), поэтому вы можете рассмотреть возможность использования Pattern и Matcher в сочетании с StringBuffer:

String input = ...;
StringBuffer sb = new StringBuffer();

Pattern p = Pattern.compile("</?(h1|h2|...)>");
Matcher m = p.matcher( input );
while( m.find() )
{
  String match = m.group();
  String replacement = ...; //get replacement for match, e.g. by lookup in a map

  m.appendReplacement( sb, replacement );
}
m.appendTail( sb );

Вы можете сделать что-то подобное с StringBuilder, но в этом случае вам придется реализовать appendReplacement и т.д. самостоятельно.

Что касается выражения, вы также можете просто попробовать и сопоставить любой тег html (хотя это может вызвать проблемы, поскольку регулярное выражение и произвольный html не очень хорошо подходят), и когда поиск не имеет результата, вы просто заменяете соответствие с самим собой.

Ответ 4

Конкретный пример, который вы предоставляете, выглядит как HTML или XHTML. Попытка редактирования HTML или XML с использованием регулярных выражений вызвана проблемами. Для такого редактирования вы, похоже, заинтересованы в том, чтобы посмотреть, как использовать XSLT. Другая возможность - использовать SAX, потоковый анализатор XML, и ваш фоновый файл будет записывать отредактированный вывод "на лету". Если текст на самом деле является HTML, вам может быть лучше использовать толерантный синтаксический анализатор HTML, такой как JSoup, для создания анализируемого представления документа (например, DOM) и манипулировать этим, прежде чем выводить его.

Ответ 5

StringBuilder поддерживается массивом char. Таким образом, в отличие от экземпляров String, он изменен. Таким образом, вы можете вызвать indexOf() и replace() на StringBuilder.

Ответ 6

Я бы сделал что-то вроде этого

    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < str.length(); i++) {
        if (tagEquals(str, i, "h1")) {
            sb.append("<big><big><big><b>");
            i += 2;
        } else (tagEquals(s, i, "/h1")) { 
            ...
        } else {
            sb.append(str.charAt(i));
        }
    }

tagEquals - это функция, которая проверяет имя тега

Ответ 7

Используйте Apache Commons StringUtils.replaceEach.

String[] searches =     new String[]{"<h1>",                "</h1>",                  "<h2>", ...};
String[] replacements = new String[]("<big><big><big><b>",  "</b></big></big></big>", "<big><big>" ...};
string = StringUtils.replaceEach(string, searches, replacements);