Ищите способ оптимизировать этот алгоритм для разбора очень большой строки

Question

Следующий класс анализирует очень большую строку (весь текст) и разбивает ее на последовательные 4-символьные строки, которые хранятся в виде кортежа.Затем каждому кортежу может быть назначена вероятность на основе расчета.Я использую это как часть монте-карло / генетического алгоритма, чтобы обучить программу распознавать язык только на основе синтаксиса (только переходы символов).

Мне интересно, есть ли более быстрый способ сделать это.Требуется около 400 мс, чтобы найти вероятность любого данного 4-символьного кортежа.Соответствующий метод _Probablity () находится в конце класса.

Это сложная вычислительная проблема, связанная с другим моим постом: Алгоритм вычисления правдоподобия функции / Метод Монте-Карло

В конечном итоге я бы хотел сохранитьэти значения в 4d-матрице.Но, учитывая, что в алфавите 26 букв, это будет ОГРОМНАЯ задача.(26x26x26x26).Если я возьму только первые 15000 символов романа, производительность улучшится, но мои данные не так полезны.

Вот метод, который анализирует текст 'source':

    private List<Tuple<char, char, char, char>> _Parse(string src)
    {
        var _map = new List<Tuple<char, char, char, char>>(); 

        for (int i = 0; i < src.Length - 3; i++)
        {
          int j = i + 1;
          int k = i + 2;
          int l = i + 3;

          _map.Add
            (new Tuple<char, char, char, char>(src[i], src[j], src[k], src[l])); 
        }

        return _map; 
    }

А вот метод _Probability:

    private double _Probability(char x0, char x1, char x2, char x3)
    {
        var subset_x0 = map.Where(x => x.Item1 == x0);
        var subset_x0_x1_following = subset_x0.Where(x => x.Item2 == x1);
        var subset_x0_x2_following = subset_x0_x1_following.Where(x => x.Item3 == x2);
        var subset_x0_x3_following = subset_x0_x2_following.Where(x => x.Item4 == x3);

        int count_of_x0 = subset_x0.Count();
        int count_of_x1_following = subset_x0_x1_following.Count();
        int count_of_x2_following = subset_x0_x2_following.Count();
        int count_of_x3_following = subset_x0_x3_following.Count(); 

        decimal p1;
        decimal p2;
        decimal p3;

        if (count_of_x0 <= 0 || count_of_x1_following <= 0 || count_of_x2_following <= 0 || count_of_x3_following <= 0)
        {
            p1 = e;
            p2 = e;
            p3 = e;
        }
        else
        {
            p1 = (decimal)count_of_x1_following / (decimal)count_of_x0;
            p2 = (decimal)count_of_x2_following / (decimal)count_of_x1_following;
            p3 = (decimal)count_of_x3_following / (decimal)count_of_x2_following;

            p1 = (p1 * 100) + e; 
            p2 = (p2 * 100) + e;
            p3 = (p3 * 100) + e; 
        }

        //more calculations omitted

        return _final; 
    }
}

EDIT - Я предоставляю больше деталей, чтобы прояснить ситуацию,

1) Строго говоря, я до сих пор работал только с английским языком, но это правда, что другие алфавиты должны будут рассматриваться.В настоящее время я хочу, чтобы программа распознавала только английский язык, подобно тому, что описано в этой статье: http://www -stat.stanford.edu / ~ cgates / PERSI /apers / MCMCRev.pdf

2) Я вычисляю вероятности n наборов символов, где n <= 4. Например, если я вычисляю общую вероятность строки «что», я бы разбил ее на эти независимые кортежи и вычислил вероятность каждогосначала индивидуально: </p>

[т] [ч]

[т] [ч] [а]

[т] [ч] [а] [т]

[t] [h] дается наибольший вес, затем [t] [h] [a], затем [t] [h] [a] [t].Поскольку я не просто рассматриваю 4-символьный кортеж как единое целое, я не смогу просто разделить экземпляры [t] [h] [a] [t] в тексте на общее число no.из 4-х кортежей в следующем.

Значение, присвоенное каждому 4-му кортежу, не может соответствовать тексту, потому что случайно многие настоящие английские слова могут никогда не появиться в тексте, и они не должны получать непропорционально низкие оценки.Усиление переходов между символами первого порядка (2 кортежа) облегчает эту проблему.Переходя к 3-кортежу, затем 4-кортеж просто уточняет расчет.

Я придумал Словарь, который просто подсчитывает, как часто в тексте встречается кортеж (аналогично тому, что предлагал Вилкс), вместо того, чтобы повторять идентичные кортежи, что является пустой тратой памяти.Это дало мне от ~ 400 мс на поиск до ~ 40 мс на поиск, что является довольно значительным улучшением.Однако я все еще должен рассмотреть некоторые другие предложения.

Answer 1

Наилучшим подходом здесь является использование разреженного хранилища и сокращение после каждого 10000 символов, например.Лучшей структурой хранения в этом случае является префиксное дерево, оно позволит быстро вычислить вероятность, обновить и разрежить хранилище.Вы можете узнать больше теории в этом javadoc http://alias -i.com / lingpipe / docs / api / com / aliasi / lm / NGramProcessLM.html

Answer 2

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

Затем вы пытаетесь найти числосоответствует в тексте текста с набором символов.Интересно, как прямой линейный поиск по исходному тексту будет сравниваться с используемыми вами операторами linq?.Where будет выделять память (что является медленной операцией), а оператор linq будет иметь накладные расходы при разборе (но здесь компилятор может сделать что-то умное).Хорошее понимание пространства поиска облегчит поиск оптимального алгоритма.

Но тогда, как уже упоминалось в комментариях, использование матрицы 26 ⁴ будет наиболееЭФФЕКТИВНАЯ.Разбор входного текста один раз и создание матрицы при разборе.Вам, вероятно, понадобится набор словарей:

SortedDictionary <int,int> count_of_single_letters; // key = single character
SortedDictionary <int,int> count_of_double_letters; // key = char1 + char2 * 32
SortedDictionary <int,int> count_of_triple_letters; // key = char1 + char2 * 32 + char3 * 32 * 32
SortedDictionary <int,int> count_of_quad_letters;   // key = char1 + char2 * 32 + char3 * 32 * 32 + char4 * 32 * 32 * 32

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

Answer 3

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

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

EDIT

Вот пример того, как я думаю, я бы сделал это в C #

class TextParser{
        private Node Parse(string src){
            var top = new Node(null);

            for (int i = 0; i < src.Length - 3; i++){
                var first = src[i];
                var second = src[i+1];
                var third = src[i+2];
                var fourth = src[i+3];

                var firstLevelNode = top.AddChild(first);
                var secondLevelNode = firstLevelNode.AddChild(second);
                var thirdLevelNode = secondLevelNode.AddChild(third);
                thirdLevelNode.AddChild(fourth);
            }

            return top;
        }
    }

    public class Node{
        private readonly Node _parent;
        private readonly Dictionary<char,Node> _children 
                         = new Dictionary<char, Node>();
        private int _count;

        public Node(Node parent){
            _parent = parent;
        }

        public Node AddChild(char value){
            if (!_children.ContainsKey(value))
            {
                _children.Add(value, new Node(this));
            }
            var levelNode = _children[value];
            levelNode._count++;
            return levelNode;
        }
        public decimal Probability(string substring){
            var node = this;
            foreach (var c in substring){
                if(!node.Contains(c))
                    return 0m;
                node = node[c];
            }
            return ((decimal) node._count)/node._parent._children.Count;
        }

        public Node this[char value]{
            get { return _children[value]; }
        }
        private bool Contains(char c){
            return _children.ContainsKey(c);
        }
    }

использование будет тогда:

var top = Parse(src);
top.Probability("test");

Answer 4

Хорошо, у меня нет времени, чтобы проработать детали, но это действительно требует

• нейронные классификационные сети (просто возьмите все с полки, даже Controllable Regex Mutilator сделает работу с гораздо большей масштабируемостью) - эвристика над грубой силой

• вы можете использовать попытки ( Patricia Tries aka Radix Trees для создания оптимизированной по пространству версии вашей структуры данных, которая может быть разреженной (словарь словарей словарей словарей ... выглядит как приближение это ко мне)

Answer 5

Я бы предложил изменить структуру данных, чтобы сделать это быстрее ...

Я думаю, Dictionary<char,Dictionary<char,Dictionary<char,Dictionary<char,double>>>> будет гораздо более эффективным, так как вы будете получать доступ к каждому "уровню" (Item1 ... Item4) при расчете ... и вы будете кэшировать результат в самом внутреннем Dictionary, так что в следующий раз вам не нужно рассчитывать вообще ..