algorithm - 最長の繰り返し部分文字列を見つける

Question

この問題を解決するための(パフォーマンス面での)最善のアプローチは何でしょうか? サフィックスツリーを使用することをお勧めしました。これは最善のアプローチですか？

Answer 1

このリンクをチェックしてください: http://introcs.cs.princeton.edu/java/42sort/LRS.java.html

/*************************************************************************
 *  Compilation:  javac LRS.java
 *  Execution:    java LRS < file.txt
 *  Dependencies: StdIn.java
 *  
 *  Reads a text corpus from stdin, replaces all consecutive blocks of
 *  whitespace with a single space, and then computes the longest
 *  repeated substring in that corpus. Suffix sorts the corpus using
 *  the system sort, then finds the longest repeated substring among 
 *  consecutive suffixes in the sorted order.
 * 
 *  % java LRS < mobydick.txt
 *  ',- Such a funny, sporty, gamy, jesty, joky, hoky-poky lad, is the Ocean, oh! Th'
 * 
 *  % java LRS 
 *  aaaaaaaaa
 *  'aaaaaaaa'
 *
 *  % java LRS
 *  abcdefg
 *  ''
 *
 *************************************************************************/


import java.util.Arrays;

public class LRS {

    // return the longest common prefix of s and t
    public static String lcp(String s, String t) {
        int n = Math.min(s.length(), t.length());
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) != t.charAt(i))
                return s.substring(0, i);
        }
        return s.substring(0, n);
    }


    // return the longest repeated string in s
    public static String lrs(String s) {

        // form the N suffixes
        int N  = s.length();
        String[] suffixes = new String[N];
        for (int i = 0; i < N; i++) {
            suffixes[i] = s.substring(i, N);
        }

        // sort them
        Arrays.sort(suffixes);

        // find longest repeated substring by comparing adjacent sorted suffixes
        String lrs = "";
        for (int i = 0; i < N - 1; i++) {
            String x = lcp(suffixes[i], suffixes[i+1]);
            if (x.length() > lrs.length())
                lrs = x;
        }
        return lrs;
    }



    // read in text, replacing all consecutive whitespace with a single space
    // then compute longest repeated substring
    public static void main(String[] args) {
        String s = StdIn.readAll();
        s = s.replaceAll("\\s+", " ");
        StdOut.println("'" + lrs(s) + "'");
    }
}

Answer 2

http://en.wikipedia.org/wiki/Suffix_arrayも参照してください。これらは非常にスペース効率が高く、Karkkainen と Sanders による「Simple Linear Work Suffix Array Construction」など、それらを生成するための合理的にプログラム可能なアルゴリズムがいくつかあります。

Answer 3

public class LongestSubString {

    public static void main(String[] args) {
        String s = findMaxRepeatedString("ssssssssssss this is a ddddddd word with iiiiiiiiiis and loads of these are ppppppppppppps");
        System.out.println(s);
    }

    private static String findMaxRepeatedString(String s) {
        Processor p = new Processor();
        char[] c = s.toCharArray();
        for (char ch : c) {
            p.process(ch);
        } 
        System.out.println(p.bigger());
        return new String(new char[p.bigger().count]).replace('\0', p.bigger().letter);
    }

    static class  CharSet {
        int count;
        Character letter;
        boolean isLastPush;

        boolean assign(char c) {
            if (letter == null) {
                count++;
                letter = c;
                isLastPush = true;
                return true;
            }
            return false;
        }

        void reassign(char c) {
            count = 1;
            letter = c;
            isLastPush = true;
        }

        boolean push(char c) {
            if (isLastPush && letter == c) {
                count++;
                return true;
            }
            return false;
        }

        @Override
        public String toString() {
            return "CharSet [count=" + count + ", letter=" + letter + "]";
        }

    }

    static class  Processor {

        Character previousLetter = null;
        CharSet set1 = new CharSet();
        CharSet set2 = new CharSet();

        void process(char c) {
            if ((set1.assign(c)) || set1.push(c)) {
                set2.isLastPush = false;
            } else if ((set2.assign(c)) || set2.push(c)) {
                set1.isLastPush = false;                
            } else {
                set1.isLastPush = set2.isLastPush = false;
                smaller().reassign(c);
            }
        }       

        CharSet smaller() {
            return set1.count < set2.count ? set1 : set2;
        }

        CharSet bigger() {
            return set1.count < set2.count ? set2 : set1;
        }

    }   
}

Answer 4

パフォーマンスに影響を与える要素が多すぎて、提供された情報だけでこの質問に答えることができません。(オペレーティング システム、言語、メモリの問題、コード自体)

アルゴリズムの効率の数学的分析を探しているだけなら、おそらく質問を変更したいと思うでしょう。

編集

「メモリの問題」と「コード」について言及したとき、すべての詳細を提供しませんでした。分析する文字列の長さは大きな要因です。また、コードは単独では機能しません。コードを有効にするには、プログラム内に配置する必要があります。このアルゴリズムの使用とパフォーマンスに影響を与えるそのプログラムの特徴は何ですか?

基本的に、テストする実際の状況が得られるまで、パフォーマンスの調整はできません。最善のパフォーマンスを発揮する可能性が高いものについて、非常に知識に基づいた推測を行うことはできますが、実際のデータと実際のコードが得られるまで、確実なことはありません。