Соответствие строки для шаблонов

Question

У меня есть 2 строки шаблона a.{var1}.{var2} и b.{var1}.{var2}.

Две строки совпадают, если var1 в первой строке совпадает с var1 во второй строке, а var2 в первой строке совпадает с var2 во второй строке.

Переменные могут быть любого порядка, например a.{var1}.{var2} и b.{var2}.{var1}.

Как эффективно сопоставить две строки?

Пример 1:

String pattern1 = "1.{var1}";
String pattern2 = "2.{var1}";

//Match True = (1.111,2.111)
//Match False = (1.121,2.111)

Пример 2:

String pattern1 = "1.{var1}.{var2}";
String pattern2 = "2.{var1}.{var2}";

//Match True = (1.11.22,2.11.22)
//Match False = (1.11.22,2.111.22)

Пример 3:

String pattern1 = "1.{var1}.{var2}";
String pattern2 = "2.{var2}.{var1}";

//Match True = (1.22.11,2.11.22)
//Match False = (1.11.22,2.111.22)

Итак, каков наилучший способ сопоставить эти 2 строки?

Я хочу сопоставить эти 2 строки, чтобы выяснить, связаны ли они с упомянутым шаблоном.Распространение этой задачи на набор строк, т. Е. Строки набора A, должны быть сопоставлены со строками в наборе B. Наконец, должны быть сформированы пары строк, которые удовлетворяют этому алгоритму сопоставления.Шаблон останется прежним при сопоставлении для всех строк из набора A в набор B.

Answer 1

Это можно сделать следующим образом:

• Пока мы проверяем, совпадают ли первая строка и первый шаблон, мы извлекаем карту значений в строке, соответствующих заполнителям (var1, var2, ...) в шаблоне;
• Пока мы проверяем, совпадают ли вторая строка и второй шаблон, мы также проверяем вторую строку по значениям заполнителей.

Это интересно, потому что заполнитель карты -> значение вычисляется один раз для пары (первая строка, первый шаблон), и может использоваться для проверки каждой пары (вторая строка, второй шаблон).

Перевод в коде: создать объект типа PatternMatcher из (первая строка, первый шаблон). Этот объект будет содержать карту valueByPlaceHolder используется для проверки других пар.

Вот соответствующие части кода.

Проверка соответствия строки и шаблона + создание карты:

private static Optional<Map<String, String>> extractValueByPlaceHolder(
        String[] sChunks, String[] patternChunks) {
    // string and pattern should have the same length
    if (sChunks.length != patternChunks.length)
        return Optional.empty();

    Map<String, String> valueByPlaceHolder = new HashMap<>(sChunks.length);
    for (int i = 0; i < patternChunks.length; i++) {
        String patternChunk = patternChunks[i];
        String sChunk = sChunks[i];
        if (isAPlaceHolder(patternChunk)) { // first char = {, last char = }
            valueByPlaceHolder.put(patternChunk, sChunk); // just get the value
        } else if (!patternChunk.equals(sChunk)) {
            // if it's not a placeholder, the chunks should be the same in the string
            // and the pattern
            return Optional.empty(); 
        }
    }
    return Optional.of(valueByPlaceHolder);
}

Проверить, совпадают ли другая строка и другой шаблон + сравнение с первой парой (строка, шаблон):

public boolean check(String[] otherChunks, String[] otherPatternChunks) {
    // other string and other pattern should have the same length, other string and string too
    if (otherChunks.length != this.chunks_length || otherChunks.length != otherPatternChunks.length)
        return false;

    for (int i = 0; i < otherChunks.length; i++) {
        String otherPatternChunk = otherPatternChunks[i];
        String otherChunk = otherChunks[i];
        // get the value from the first string if a it's placeholder, else keep the pattern chunk 
        String expectedChunk = this.valueByPlaceHolder
                .getOrDefault(otherPatternChunk, otherPatternChunk);

        // the chunk is neither equal to the value of the placeholder, nor to the chunk of the pattern 
        if (!expectedChunk.equals(otherChunk))
                return false;
    }
    return true;
}

Answer 2

Вы можете использовать следующие методы класса String:

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

Проверяет, соответствует ли указанная область этой строки указанной области аргумента String.Область имеет длину len и начинается с индекса toffset для этой строки и ooffset для другой строки.

Для игнорирования регистра:

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

Дополнительная информация: https://docs.oracle.com/javase/tutorial/java/data/comparestrings.html

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

Answer 3

Удалите шаблоны из строки, извлеките переменные из строки, разделив их вокруг точки (при условии, что в ваших переменных нет точек), поместите их вНабор (Наборы не сохраняют порядок и, следовательно, автоматически решают вашу проблему с игнорированием позиции), Проверьте равенство Наборов .

Демонстрация работы: https://ideone.com/5MwOHC

Пример кода:

final static String pattern1head = "blablabla.";
final static String pattern2head = "yada yada.";

private static Set<String> extractVars(String v){
    if      (v.startsWith(pattern1head)) { v = v.replace(pattern1head,""); }
    else if (v.startsWith(pattern2head)) { v = v.replace(pattern2head,""); }
    else                                 { return null; }           

    return new HashSet<String>(Arrays.asList(v.split("\\.")));
}

private static void checkEquality(String v1, String v2) {
    System.out.println("\n"+v1+" == "+v2+" ? " + extractVars(v1).equals(extractVars(v2)));  
} 


public static void main (String[] args) throws java.lang.Exception {
    String v1 = "blablabla.123.456";
    String v2 = "yada yada.123.456";
    String v3 = "yada yada.456.123";
    String v4 = "yada yada.123.456789";

    checkEquality(v1,v2);
    checkEquality(v1,v3);
    checkEquality(v1,v4);
    checkEquality(v2,v3);
    checkEquality(v2,v4);
}

Вывод:

blablabla.123.456 == yada yada.123.456 ? true

blablabla.123.456 == yada yada.456.123 ? true

blablabla.123.456 == yada yada.123.456789 ? false

yada yada.123.456 == yada yada.456.123 ? true

yada yada.123.456 == yada yada.123.456789 ? false

Answer 4

Полагаю следующее:

string[] arr1 = pattern1.split
string[] arr2 = pattern2.split
int hash1 = arr1[0].hashCode() + arr1[1].hashCode();
int hash2 = arr2[0].hashCode() + arr2[1].hashCode();
if(hash1 = hash2)=> pattern1 == pattern2

Answer 5

Возможно, это не самый эффективный способ сделать это, но он дает ожидаемый результат.

01/05: Код обновлен после ошибки, указанной Оле в комментариях ::

private boolean compareStr(String a, String b) {
    ArrayList<String> aList = new 
    ArrayList<String>(Arrays.asList(a.split("\\.")));
    ArrayList<String> bList = new ArrayList<String>(Arrays.asList(b.split("\\.")));
    bList.remove(0);
    aList.remove(0);

    if(aList.size() != bList.size())
            return false;

    boolean aMatchFlag = false;
    for(int i=0; i< aList.size(); i++){
        if (!bList.contains(aList.get(i))) {
            return false;
        }
    }
    aMatchFlag = true;
    System.out.println("All elements of A are present in B");
    boolean bMatchFlag = false;
    for(int i=0; i< bList.size(); i++){
        if (!aList.contains(bList.get(i))) {
            return false;
        }
    }
    bMatchFlag = true;
    System.out.println("All elements of B are present in A");

    if(aMatchFlag && bMatchFlag)
            return true;
    else
            return false;
}

Для тех, кто также ищет производительность кода

Input:1.11.11, 2.11.11.11
Compilation time: 1.45 sec, absolute running time: 0.24 sec, cpu time: 0.26 sec, memory peak: 18 Mb, absolute service time: 1,7 sec

Input:1.11.11, 2.11.22
Compilation time: 1.25 sec, absolute running time: 0.24 sec, cpu time: 0.23 sec, memory peak: 18 Mb, absolute service time: 1,49 sec

Input:1.11.2, 2.11.22
Compilation time: 1.34 sec, absolute running time: 0.24 sec, cpu time: 0.24 sec, memory peak: 18 Mb, absolute service time: 1,58 sec


Input:1.11.2, 2.11.111
Compilation time: 1.65 sec, absolute running time: 0.28 sec, cpu time: 0.32 sec, memory peak: 18 Mb, absolute service time: 1,94 sec

Answer 6

Используйте String.split(), а затем String.equals() в результирующих элементах массива, обрабатывая три случая отдельно.

После разделения сначала убедитесь, что оба полученных массива имеют одинаковую длину (если они не совпадают). Также используйте String.equals() для проверки того, что первый элемент - "1" и "2", если это требуется. Затем уточните, равна ли длина 2 или 3. Если длина равна 2, убедитесь, что это совпадение, как в вашем примере 1; снова используйте String.equals() для элементов массива. Если длина равна 3, вам нужно проверить оба порядка переменных частей в соответствии с вашими двумя примерами 2 и 3.

Помните, что аргумент String.split() является регулярным выражением и что точка имеет особое значение в регулярных выражениях. Поэтому вам нужно использовать .split("\\."), а не .split(".").

Он тоже должен работать довольно быстро. Однако не начинайте оптимизацию, пока не поймете, что вам нужна более высокая производительность. Читаемость - король.

Удачного кодирования.

Редактировать: Предполагая, что у вас было время написать собственное решение, я представляю свое для вдохновения и для сравнения со своим (и другими ответами, если хотите).

public static boolean match(String s1, String s2) {
    String[] a1 = s1.split("\\.", 4);
    String[] a2 = s2.split("\\.", 4);
    if (a1.length != a2.length) {
        return false;
    }
    if (a1[0].equals("1") && a2[0].equals("2")) {
        if (a1.length == 2) {
            return a1[1].equals(a2[1]);
        } else if (a1.length == 3) {
            return (a1[1].equals(a2[1]) && a1[2].equals(a2[2]))
                    || (a1[1].equals(a2[2]) && a1[2].equals(a2[1]));
        }
    }
    return false;
}

Попробуем 6 примеров из вопроса:

    System.out.println("(1.111,2.111)      " + match("1.111", "2.111"));
    System.out.println("(1.121,2.111)      " + match("1.121", "2.111"));
    System.out.println("(1.11.22,2.11.22)  " + match("1.11.22", "2.11.22"));
    System.out.println("(1.11.22,2.111.22) " + match("1.11.22", "2.111.22"));
    System.out.println("(1.22.11,2.11.22)  " + match("1.22.11", "2.11.22"));
    System.out.println("(1.11.22,2.111.22) " + match("1.11.22", "2.111.22"));

Это печатает:

(1.111,2.111)      true
(1.121,2.111)      false
(1.11.22,2.11.22)  true
(1.11.22,2.111.22) false
(1.22.11,2.11.22)  true
(1.11.22,2.111.22) false