Как мне найти повторяющиеся последовательности слов

Question

Мне нужно обнаружить наличие нескольких блоков столбчатых данных только по их заголовкам.О данных ничего не известно, кроме заголовочных слов, которые различны для каждого набора данных.

Важно отметить, что заранее неизвестно, сколько слов содержится в каждом блоке и, следовательно, сколько блоков.

Не менее важно, что список слов всегда относительно короткий - меньше, чем20.

Итак, учитывая список или массив заголовочных слов, таких как:

Opt
Object
Type
Opt
Object
Type
Opt
Object
Type

, какой самый эффективный способ определить, что он полностью состоит из повторяющейся последовательности:

Opt
Object
Type

Это должно быть точное совпадение, поэтому моя первая мысль состоит в том, чтобы искать [1+] в поисках совпадений с [0], называя их индексами n, m, ... Затем, если они равноудалены, проверяют [1] == [n + 1] == [m + 1] и [2] == [n + 2] == [m + 2] и т. Д.

РЕДАКТИРОВАТЬ: должно работать для словаустанавливает, где некоторые слова повторяются внутри блока, поэтому

Opt
Opt
Object
Opt
Opt
Object

представляет собой набор из 2

Opt
Opt
Object

Answer 1

Если список состоит из x повторяющихся групп, так что каждая группа содержит n элементов ...

Мы знаем, что есть хотя бы 1 группа, поэтому мы посмотрим, есть ли 2 повторяющиеся группы, протестируйте, сравнивпервая половина списка и вторая половина.

1) Если вышеупомянутое верно, мы знаем, что решение является фактором 2

2) Если вышеупомянутое неверно, мы переходим кследующее по величине простое число, которое делится на общее количество слов ...

На каждом шаге мы проверяем равенство между списками, если мы находим его, то знаем, что у нас есть решение с этим фактором.

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

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

---

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

Answer 2

Может ли последовательность единиц содержать собственные повторения? Вы знаете длину последовательности единиц?

, например

ABCABCABCDEFABCABCABCDEFABCABCABCDEF

где единичная последовательность ABCABCABCDEF

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

Если ответ отрицательный, используйте этот вариант Алгоритм обнаружения циклов Флойда , чтобы определить последовательность единиц:

• Инициализировать указатели P1 и P2 в начале последовательности.
• Для каждого нового элемента, увеличивать указатель P1 каждый раз, и увеличивать указатель P2 каждый раз (держите счетчик для этого).

• Если P1 указывает на идентичные элементы P2, вы нашли последовательность единиц.

• Теперь повторите всю оставшуюся последовательность, чтобы убедиться, что она состоит из дубликатов.

---

ОБНОВЛЕНИЕ: вы разъяснили свою проблему, заявив, что последовательность может содержать собственные повторения. В этом случае используйте алгоритм поиска циклов, но гарантированно найти только потенциальные циклы. Поддерживайте его на протяжении всей последовательности и используйте следующий конечный автомат, начиная с состояния 1:

Состояние 1: не найдено ни одного цикла, который работает; продолжай смотреть Когда алгоритм поиска цикла находит потенциальный цикл, убедитесь, что вы получили 2 копии предварительной последовательности единиц из P, и перейдите в состояние 2. Если вы достигли конца ввода, перейдите в состояние 4.

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

Состояние 3: вход является повторением последовательности единиц, если конец ввода состоит из полных повторений последовательности единиц. (Если он находится в середине последовательности единиц, например, ABCABCABCABCAB, то последовательность единиц найдена, но она не состоит из полных повторений.)

Состояние 4: последовательность единиц не найдена.

В моем примере (повторяя ABCABCABCDEF) алгоритм начинается с поиска ABCABC, который переводит его в состояние 2, и будет оставаться там до тех пор, пока не достигнет первого DEF, который вернет его в состояние 1, затем, вероятно, переходите назад и вперед между состояниями 1 и 2, пока он не достигнет 2-го ABCABCABCDEF, после чего он снова войдет в состояние 2, и в конце ввода он будет в состоянии 3.

Answer 3

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

package com.example.algorithms;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

interface Processor<T> {
    public void process(T element);
}

public class RepeatingListFinder<T> implements Processor<T> {

    private List<T> unit_sequence = new ArrayList<T>();
    private int repeat_count = 0;
    private int partial_matches = 0;
    private Iterator<T> iterator = null;

    /* Class invariant:
     * 
     * The sequence of elements passed through process()
     * can be expressed as the concatenation of
     *        the unit_sequence repeated "repeat_count" times,
     *   plus the first "element_matches" of the unit_sequence.
     * 
     * The iterator points to the remaining elements of the unit_sequence,
     * or null if there have not been any elements processed yet.
     */

    public void process(T element) {
        if (unit_sequence.isEmpty() || !iterator.next().equals(element))
        {
            revise_unit_sequence(element);
            iterator = unit_sequence.iterator();
            repeat_count = 1;
            partial_matches = 0;
        }
        else if (!iterator.hasNext())
        {
            iterator = unit_sequence.iterator();
            ++repeat_count;
            partial_matches = 0;
        }
        else
        {
            ++partial_matches;
        }
    }

    /* Unit sequence has changed. 
     * Restructure and add the new non-matching element. 
     */
    private void revise_unit_sequence(T element) {
        if (repeat_count > 1 || partial_matches > 0)
        {
            List<T> new_sequence = new ArrayList<T>();
            for (int i = 0; i < repeat_count; ++i)
                new_sequence.addAll(unit_sequence);
            new_sequence.addAll(
                    unit_sequence.subList(0, partial_matches));

            unit_sequence = new_sequence;
        }
        unit_sequence.add(element);
    }

    public List<T> getUnitSequence() { 
        return Collections.unmodifiableList(unit_sequence);
    }
    public int getRepeatCount() { return repeat_count; }
    public int getPartialMatchCount() { return partial_matches; }
    public String toString()
    {
        return "("+getRepeatCount()
        +(getPartialMatchCount() > 0 
            ? (" "+getPartialMatchCount()
                +"/"+unit_sequence.size())
            : "")
        +") x "+unit_sequence;
    }

    /********** static methods below for testing **********/

    static public List<Character> stringToCharList(String s)
    {
        List<Character> result = new ArrayList<Character>();
        for (char c : s.toCharArray())
            result.add(c);
        return result;
    }

    static public <T> void test(List<T> list)
    {
        RepeatingListFinder<T> listFinder 
            = new RepeatingListFinder<T>();
        for (T element : list)
            listFinder.process(element);
        System.out.println(listFinder);
    }

    static public void test(String testCase)
    {
        test(stringToCharList(testCase));
    }

    static public void main(String[] args)
    {
        test("ABCABCABCABC");
        test("ABCDFTBAT");
        test("ABABA");
        test("ABACABADABACABAEABACABADABACABAEABACABADABAC");
        test("ABCABCABCDEFABCABCABCDEFABCABCABCDEF");
        test("ABABCABABCABABDABABDABABC");      
    }
}

Это потоковый подход (с O (N) временем выполнения и O (N) наихудшими требованиями к пространству); если обрабатываемый List<T> уже существует в памяти, должна быть возможность переписать этот класс для обработки List<T> без каких-либо дополнительных требований к пространству, просто отслеживая количество повторений и частичное совпадение, используя List.subList ( ) для создания последовательности единиц, которая представляет собой вид первых K элементов списка ввода.

Answer 4

Мое решение, которое работает по желанию, возможно, наивно.Он имеет преимущество в простоте.

String[]                            wta;                                    // word text array
...
INTERVAL:
for(int xa=1,max=(wta.length/2); xa<=max; xa++) {
    if((wta.length%xa)!=0) { continue; }                                    // ignore intervals which don't divide evenly into the words
    for(int xb=0; xb<xa; xb++) {                                            // iterate the words within the current interval
        for(int xc=xb+xa; xc<wta.length; xc+=xa) {                          // iterate the corresponding words in each section
            if(!wta[xb].equalsIgnoreCase(wta[xc])) { continue INTERVAL; }   // not a cycle
            }
        }
    ivl=xa;
    break;
    }