Какой алгоритм сопоставления с образцом подходит для моего случая?

В качестве предложения, и даже если это не «полный ответ» на вашу проблему, сравнение строк обычно является «тяжелой» операцией (даже если вы сначала проверяете их длину, что, по сути, является одной из первых вещей, которые equals() метод уже работает при сравнении строк)

Что я предлагаю сделать дальше: создать метод dummy hashcode()-like. Это будет не настоящий hashcode(), а число, связанное с порядком, в котором это слово было прочитано вашим кодом. Что-то вроде криптографического метода, но намного проще.

Обратите внимание, что string.hashCode() не будет работать, так как слово «Привет» из первого документа не вернет тот же хэш-код, что и слово «Привет» из второго документа.

Данные "Потепление" - Преконверсия

Представьте, что у вас есть общий HashMap<String,Integer> (myMap), ключ которого является строкой, а значение — целым числом. Обратите внимание, что хеширование HashMap в java со строковыми ключами менее 10 символов (что обычно бывает в английском языке) происходит невероятно быстро. Без какой-либо проверки просто поместите каждое слово с его значением счетчика:

  myMap.put(yourString, ++counter);  

Допустим, у вас есть 2 документа:

 1.txt-   Welcome mate what are you doing here 
     
 2.txt-   Mate I was here before are you dumb

Я предполагаю, что вы уже перевели все слова в нижний регистр и удалили дубликаты. Вы начинаете читать первый документ и присваиваете каждому слову номер. Карта будет выглядеть так:

        KEY                     VALUE
       welcome                    1
       mate                       2
       what                       3
       are                        4
       you                        5
       doing                      6
       here                       7

Теперь со вторым документом. Если ключ повторяется, метод put() обновит его значение. Так:

        KEY                     VALUE
       welcome                    1
       mate                       8
       what                       3
       are                        13
       you                        14
       doing                      6
       here                       11
         I                        9
       was                        10
       before                     12
       dumb                       15

После завершения вы создаете еще один HashMap<Integer,String> (reverseMap) в обратном порядке:

       KEY                    VALUE
       1                       welcome
       8                       mate
       3                       what
       13                       are
       14                       you
       6                       doing
       11                       here
        9                        I
       10                        was
       12                     before
       15                       dumb

Вы конвертируете оба документа в список целых чисел, поэтому они выглядят так:

 1.txt-   Welcome mate what are you doing here
 2.txt-   Mate I was here before are you dumb

К:

 listOne - [1, 8, 3, 13, 14, 6, 11]
 listTwo - [8, 9, 10, 11, 12, 13, 14, 15]

Повторяющиеся слова, позиции и последовательности

Чтобы найти дубликаты в обоих документах:

• Сначала создайте глубокий клон одного из списков, например, listTwo. Глубокий клон List из Integers относительно легко выполнить. Назвать его listDuplicates так и будет его целью.

     List<Integer> listDuplicates = new ArrayList<>();
      for (Integer i:listTwo)
            listDuplicates.add(new Integer(i));
  

• Звоните retainAll:

ListDuplicates.retainAll(listOne);

Результат будет:

listDuplicates- [8,11,13,14]

Итак, из listOne.size()+listTwo.size() = 15 слов, найденных в 2 документах, 4 являются дубликатами, а 11 уникальны.

Чтобы получить преобразованные значения, просто вызовите:

for (Integer i : listDuplicates)
 System.out.println(reverseMap.get(i)); // mate , here, are, you

Теперь, когда дубликаты идентифицированы, listOne и listTwo теперь также можно использовать, чтобы:

• Определите позицию в каждом списке (чтобы мы могли получить разницу в позициях этих слов). Первое слово будет иметь значение -1, так как оно первое и не имеет разницы с предыдущим, но не обязательно будет означать, что они являются последовательными с любым другим (это просто первые дубликаты).

Если следующий элемент имеет значение -1, это означает, что [8] и [11] также будут последовательными:

          doc1   doc2   difDoc1     difDoc2
    [8]     2      1     -1  (0-1)   -1  (0-1)
    [11]    7      4     -5  (2-7)   -3  (1-4)
    [13]    4      6      3  (7-4)   -2  (4-6)
    [14]    5      7     -1  (4-5)   -1  (6-7)

В этом случае расстояние, показанное в [14] с его предыдущим дубликатом (разница между [13] и [14]), одинаково в обоих документах: -1: это означает, что не только дубликаты, но и оба, следовательно, помещены в оба документа.

Следовательно, мы нашли не только повторяющиеся слова, но и повторяющуюся последовательность из двух слов между этими строками:

[13][14]--are you

Тот же механизм (определение разницы -1 для одной и той же переменной в обоих документах) также поможет найти полную повторяющуюся последовательность из 2 или более слов. Если все дубликаты показывают разницу -1 в обоих документах, это означает, что мы нашли полную повторяющуюся строку:

В этом примере это показано яснее:

   doc1- "here i am" [4,5,6]
   doc2- "here i am" [4,5,6]

ListDuplicates - [4,5,6]

              doc1   doc2   difDoc1     difDoc2
        [4]    1      1      -1  (0-1)   -1  (0-1)
        [5]    2      2      -1  (1-2)   -1  (1-2)
        [6]    3      3      -1  (2-3)   -1  (2-3)
      

Все различия равны -1 для одной и той же переменной в обоих документах -> все дубликаты находятся рядом друг с другом в обоих документах -> Предложение точно такое же в обоих документах. Итак, на этот раз мы нашли полную повторяющуюся строку из 3 слов.

[4][5][6] -- here i am

Помимо этого поиска повторяющихся последовательностей, эта таблица различий также была бы полезна при вычислении дисперсии, медианы,... из повторяющихся слов, чтобы получить некий фактор «сходства» (что-то вроде базового ориентировочного значения равенства между документы. Ни в коем случае не окончательные, но как-то полезные)

Уникальные значения — полезны для получения индикативного показателя, не связанного с капиталом?

Подобные механизмы будут использоваться для получения этих уникальных значений. Например, удалив дубликаты из reverseMap:

for (Integer i: listDuplicates)
    reverseMap.remove(i);

Теперь reverseMap содержит только уникальные значения. reverseMap.size() = 11

   KEY                     VALUE
   1                       welcome
   3                       what
   6                       doing
   9                       I
   10                      was
   12                      before
   15                      dumb

Чтобы получить уникальные слова:

ReverseMap.values() = {welcome,what,doing,I,was,before,dumb}

Если вам нужно знать, какие уникальные слова из какого документа, вы можете использовать reverseMap (поскольку списки могут быть изменены после того, как вы выполните для них такие методы, как continueAll):

• Подсчитайте количество слов из 1-го документа. На этот раз 7.
• Если ключ reverseMap <=7, это уникальное слово происходит из 1-го документа. {welcome,what,doing}
• Если ключ > 7, это уникальное слово исходит из 2-го документа. {I,was,before,dumb}

Фактор уникальности может быть и другим показательным, таким образом, отрицательным (поскольку мы здесь ищем сходство). Все еще может быть очень полезным.

Equals и hashCode - избегать

Поскольку метод hashcode() для строк не будет возвращать одно и то же значение для двух одинаковых слов (только для двух одинаковых ссылок на строковые объекты), здесь он работать не будет. String.equals() метод работает путем сравнения символов (также проверяется длина, как вы делаете вручную), что было бы полным излишеством при использовании для больших документов:

public boolean equals(Object anObject) {  
      if (this == anObject) {  
          return true;  
      }  
      if (anObject instanceof String) {  
          String anotherString = (String) anObject;  
          int n = value.length;  
          if (n == anotherString.value.length) {  
              char v1[] = value;  
              char v2[] = anotherString.value;  
              int i = 0;  
              while (n-- != 0) {  
                  if (v1[i] != v2[i])  
                          return false;  
                  i++;  
              }  
              return true;  
          }  
      }  
      return false;  
  }  

Мое мнение состоит в том, чтобы максимально избегать этого, особенно hashCode() никогда не следует использовать, так как:

String one = "hello";
String two = "hello"; 

one.hashCode() != two.hashCode()

Есть исключение, но только когда компилятор интернирует строки; Как только вы загрузите тысячи из них, они больше никогда не будут использоваться компилятором. В тех редких случаях, когда оба объекта String ссылаются на один и тот же адрес кэшированной памяти, это также будет верно:

one.hashCode() == two.hashCode() --> true
one == two --> true

Но это действительно необычные исключения, и как только стажировка строк не сработает, эти hashCodes не будут равны, и оператор == для сравнения строк вернет false, даже если строки содержат одно и то же значение (как обычно, потому что он работает, сравнивая их адреса памяти).

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

(1) индексировать или группировать документы таким образом, чтобы можно было идентифицировать возможные совпадения;

(2) Определить документы-кандидаты, которые могут быть совпадением, на основе этих индексов/кластеров;

(3) Для каждого совпадения кластера или индекса иметь алгоритм оценки, который оценивает сходство данной пары документов.

Существует несколько способов решения (1) и (3), в зависимости от характера и количества документов. Варианты для рассмотрения:

• Для определенных наборов данных (1) может быть таким же простым, как индексирование необычных слов/комбинаций слов.
• Для более сложных документов и/или больших наборов данных вам нужно будет сделать что-то, что иногда называют «уменьшением измерения»: вместо кластеризации по общим комбинациям слов вам нужно будет кластеризовать по комбинациям общих функций, где каждая функция идентифицируется набор слов. Посмотрите на метод извлечения признаков, который иногда называют «скрытое семантическое индексирование» — по сути, вы математически моделируете документы как матрицу «слов на признак», умноженную на «функция на документ», а затем разлагая полученную матрицу на множители. приблизительный набор функций, а также взвешенный список слов, составляющих каждую функцию
• Затем, когда у вас есть средство идентификации набора слов/функций для индексации, вам понадобится какая-то функция индексации, которая будет означать, что совпадения документов-кандидатов имеют идентичные/похожие индексные ключи. Посмотрите на косинусное сходство и «хеширование с учетом местоположения», такое как SimHash.
• Затем для (3) при наличии небольшого набора документов-кандидатов (или документов, которые группируются вместе в вашей системе хеширования) вам нужна метрика сходства. Опять же, какой метод подходит, зависит от ваших данных, но концептуально один из способов, которым вы могли бы представить это как «для каждого предложения в документе X, найти наиболее похожий документ в документе Y и оценить его сходство; получить «оценку плагиата», которую его сумма этих значений». Существуют различные способы определения «показателя сходства» между двумя строками: например. самая длинная общая подпоследовательность, расстояние редактирования, количество общих пар/последовательностей слов...

Как вы, наверное, догадались из всего этого, не существует единого алгоритма, который подарит вам именно то, что вам нужно на тарелке. (Вот почему этой проблеме занимаются целые компании и исследовательские отделы...) Но, надеюсь, вышеизложенное даст вам некоторые подсказки.