более быстрый способ обнаружить n-грамм в строке? - PullRequest
Новая
       60

более быстрый способ обнаружить n-грамм в строке?

1 голос
/ 02 января 2012

Я нашел это решение на SO, чтобы обнаружить n-граммы в строке: (здесь: Генерация N-граммы из предложения ) 

import java.util.*;

public class Test {

    public static List<String> ngrams(int n, String str) {
        List<String> ngrams = new ArrayList<String>();
        String[] words = str.split(" ");
        for (int i = 0; i < words.length - n + 1; i++)
            ngrams.add(concat(words, i, i+n));
        return ngrams;
    }

    public static String concat(String[] words, int start, int end) {
        StringBuilder sb = new StringBuilder();
        for (int i = start; i < end; i++)
            sb.append((i > start ? " " : "") + words[i]);
        return sb.toString();
    }

    public static void main(String[] args) {
        for (int n = 1; n <= 3; n++) {
            for (String ngram : ngrams(n, "This is my car."))
                System.out.println(ngram);
            System.out.println();
        }
    }
}

=> этот бит кода занимает самое большое время обработки (28 секунд для обнаружения 1 грамма, 2 грамма, 3 грамма и 4 грамма для моего корпуса: 4 МБ необработанного текста) по сравнению с миллисекундами для других операций (удаление стоп-слов и т. д.)

Кто-нибудь знает о решениях на Java, которые бы работали быстрее, чем решения с циклическим циклом, представленные выше? (Я думал о многопоточности, использовании коллекций или, может быть, о творческих способах разбить строку ...?) Спасибо!

Ответы [ 2 ]

3 голосов
/ 02 января 2012

Вы можете попробовать что-то вроде этого: 

public class NGram {

    private final int n;
    private final String text;

    private final int[] indexes;
    private int index = -1;
    private int found = 0;

    public NGram(String text, int n) {
        this.text = text;
        this.n = n;
        indexes = new int[n];
    }

    private boolean seek() {
        if (index >= text.length()) {
            return false;
        }
        push();
        while(++index < text.length()) {
            if (text.charAt(index) == ' ') {
                found++;
                if (found<n) {
                    push();
                } else {
                    return true;
                }
            }
        }
        return true;
    }

    private void push() {
        for (int i = 0; i < n-1; i++) {
            indexes[i] = indexes[i+1];
        }
        indexes[n-1] = index+1;
    }

    private List<String> list() {
        List<String> ngrams = new ArrayList<String>();
        while (seek()) {
            ngrams.add(get());
        }
        return ngrams;
    }

    private String get() {
        return text.substring(indexes[0], index);
    }
}

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

Обновление: Это вывод, который я получаю, работая над текстом, упомянутым выше, ngram 1-4. Я использую 2 ГБ памяти, чтобы определить влияние на сборку во время пробежек. Я запускал несколько раз, чтобы увидеть влияние компилятора горячей точки. 

Loop 01 Code mine ngram 1 time 071ms ngrams 294121
Loop 01 Code orig ngram 1 time 534ms ngrams 294121
Loop 01 Code mine ngram 2 time 016ms ngrams 294120
Loop 01 Code orig ngram 2 time 360ms ngrams 294120
Loop 01 Code mine ngram 3 time 082ms ngrams 294119
Loop 01 Code orig ngram 3 time 319ms ngrams 294119
Loop 01 Code mine ngram 4 time 014ms ngrams 294118
Loop 01 Code orig ngram 4 time 439ms ngrams 294118

Loop 10 Code mine ngram 1 time 013ms ngrams 294121
Loop 10 Code orig ngram 1 time 268ms ngrams 294121
Loop 10 Code mine ngram 2 time 014ms ngrams 294120
Loop 10 Code orig ngram 2 time 323ms ngrams 294120
Loop 10 Code mine ngram 3 time 013ms ngrams 294119
Loop 10 Code orig ngram 3 time 412ms ngrams 294119
Loop 10 Code mine ngram 4 time 014ms ngrams 294118
Loop 10 Code orig ngram 4 time 423ms ngrams 294118
0 голосов
/ 02 января 2012

Выполнение около 5 мегапикселей текста Lorus Ipsum через код, который вы ввели, обычно занимало чуть более 7 секунд для обнаружения 1 - 4 н-граммов.Я переработал код, чтобы составить список самых длинных n-грамм, а затем перебрать этот список, получая списки последовательно более коротких n-грамм.При тестировании на тот же текст ушло около 2,6 секунды.Кроме того, это заняло намного меньше памяти.

import java.util.*;

public class Test {

    public static List<String> ngrams(int max, String val) {
        List<String> out = new ArrayList<String>(1000);
        String[] words = val.split(" ");
        for (int i = 0; i < words.length - max + 1; i++) {
            out.add(makeString(words, i,  max));
        }
        return out;
    }

    public static String makeString(String[] words, int start, int length) {
        StringBuilder tmp= new StringBuilder(100);
        for (int i = start; i < start + length; i++) {
            tmp.append(words[i]).append(" ");
        }
        return tmp.substring(0, tmp.length() - 1);
    }

    public static List<String> reduceNgrams(List<String> in, int size) {
        if (1 < size) {
            List<String> working = reduceByOne(in);
            in.addAll(working);
            for (int i = size -2 ; i > 0; i--) {
                working = reduceByOne(working);
                in.addAll(working);
            }
        }
        return in;
    }

    public static List<String> reduceByOne(List<String> in) {
        List<String> out = new ArrayList<String>(in.size());
        int end;
        for (String s : in) {
            end = s.lastIndexOf(" ");
            out.add(s.substring(0, -1 == end ? s.length() : end));  
        }
        //the last one will always reduce twice - words 0, n-1 are in the loop this catches the words 1, n
        String s = in.get(in.size() -1);
        out.add(s.substring(s.indexOf(" ")+1));
        return out;
    }

    public static void main(String[] args) {
        long start;
        start = System.currentTimeMillis();
        List<String> ngrams = ngrams(3, "Your text goes here, actual mileage may vary");
        reduceNgrams(ngrams, 3);
        System.out.println(System.currentTimeMillis() - start);
    }
}
...