Группировка миллионов строк с подстановкой

Question

У меня есть большое количество (XXM-XXXM) строк, которые выглядят как (маленький образец):

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

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

Спасибо!

Answer 1

Отказ от ответственности: я никогда раньше не решал подобную проблему.

Я могу придумать пару способов подумать о вашей проблеме:

• вы пытаетесь сгруппировать каждую строку в набор кластеров
  • проверка в алгоритмах обработки данных
• разница между каждой строкой в ​​кластере будет небольшой, между линиями из двух разных кластеров будет значительно больше
• Вы можете быстро собрать похожие линии, сравнив пересечение двух линий: set(line1.split) & set(line2.split) - количество элементов в результирующем наборе является показателем того, насколько близки эти две линии.

Немного кода на Python может выглядеть так:

import fileinput

CLUSTER_COUNT = 5
MAX_DISTANCE = 5

def main():
    clusters = [Cluster() for i in range(CLUSTER_COUNT)]
    MAXDISTANCE = 3
    for line in  fileinput.input():
        words = set(line.split())
        cluster = sorted(clusters, key=lambda c: c.distanceTo(words))[0]
        cluster.addLine(words, line)

    # print out results (FIXME: write clusters to separate files)
    for cluster in clusters:
        print "CLUSTER:", cluster.intersection
        for line in cluster.lines:
            print line
        print "-" * 80
        print

class Cluster(object):
    def __init__(self):
        self.intersection = set()
        self.lines = []
    def distanceTo(self, words):
        if len(self.intersection) == 0:
            return MAX_DISTANCE 
        return len(words) - len(self.intersection & words)
    def addLine(self, words, line):
        self.lines.append(line) 
        if len(self.intersection) == 0:
            self.intersection = words
        else:
            self.intersection = self.intersection & words

if __name__ == '__main__':
    main()

Если вы запустите его на своих основных данных, у вас должно получиться несколько кластеров. Примечание. Измените код, чтобы записать кластеры в отдельные файлы. Я думаю, что вы захотите снова запустить кластеры через код, рекурсивно, пока не найдете интересующие вас подмножества.

Answer 2

Что я хотел бы сделать, это написать распознаватель параметров .Это распознает следующие подстроки (когда они окружены пробелами) в качестве параметров:

• десятичное число
• abcd , где a, b, c, d - десятичные числа
• имя файла .php

Без сомнения, их будет больше, но список не должен быть слишком большим.Затем вы заменяете каждый параметр заполнителем:% d,% url,% phpfile.Теперь вы можете просто отсортировать строки.

Вы можете найти нераспознанные типы параметров, просматривая выходные строки, которые встречаются редко.Например, если есть тип параметра ч: м: с для времени суток, строки, содержащие этот незамещенный параметр, будут уникальными или почти такими, и вы можете найти этот новый тип параметра, просто просматривая глазасписок из 100 или более «почти уникальных» строк.Затем добавьте ч: м: с в свой список, замените все такие вхождения на% time и запустите его снова.

Answer 3

После прочтения на страницах из CRM114 Управляемого Mugeator Regex :

Спам - это большая цель CRM114, но это не специализированный инструмент только для электронной почты. CRM114 используется для сортировки веб-страниц, резюме, записей в блогах, файлов журналов и многих других вещей. Точность может достигать 99,9%. Другими словами, CRM114 учится и учится быстро.

Короче говоря, это может быть именно то, что вам нужно. И вы можете рассчитывать на это для оптимизации.

Answer 4

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

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

когда сопоставление выполнено, мы создаем сегмент с группой диапазонов значений 1: (0-10) (или, как в зависимости от значения), группой 2: (10-20) ..... и так далее ... Поскольку мы говорили, что аналогичная строка должна иметь одинаковое значение, аналогичная строка помещается в одно и то же ведро

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

Answer 5

Интересный вопрос ... Просто стихийная идея, которая может быть закодирована довольно быстро:

• Решите для каждого слова, является ли оно data (11.22.33.55, 3829, somepage.php и т. д.) или описание (загрузка, подключение, страница и т. д.) путем подсчета частоты каждого слова в образце набора данных. Описание слов предположительно встречается значительно чаще, чем конкретное data word.Вам нужно настроить порог, чтобы найти тот, который разбивает слова на две категории.Если это не работает для всех случаев, например, потому что есть IP-адрес, который встречается очень часто, черный список должен исправить это.
• Обрабатывать каждую строку, вычисляя сигнатуру из набора ее description только слова (строковый хэш составных description слов должен работать).Подсчитайте вхождение каждой подписи.

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

В Python в качестве структур данных я бы попытался использовать специальный (исполняемый) тип данных dict Counter .

Answer 6

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

Answer 7

Я бы сделал что-то подобное.

map<string, int> mStringToInt;

struct structOneRecord
{   
    vector<int> vWords; 
    vector<vector<int>> vLines; // All the Lines under this record

    vector<int> vIndexOfMutableWords;

    bool operator < (const structOneRecord &n) const
    {
        if(vWords.size() != n.vWords.size())
            return vWords.size() < n.vWords.size();
        else
        {           
            // Count diferences     
            vector<int> vCurrentIndexs;         
            for(int i=0; i<vWords.size(); i++)
            {
                if(vWords[i] != n.vWords[i])                                
                    vCurrentIndexs.push_back(i);                                    
            }

            if(vCurrentIndexs.size() == 0)
                return false;

            int iHalf = vWords.size() / 2; // The diferences can't be bigger than hald the phrase
            if(vCurrentIndexs.size() < iHalf)
            {
                if(vIndexOfMutableWords.size() == 0)
                    return false;
                else
                {
                    if(vIndexOfMutableWords.size() == vCurrentIndexs.size())
                    {
                        for(int i=0; i<vIndexOfMutableWords.size(); i++)
                        {
                            if(vIndexOfMutableWords[i] != vCurrentIndexs[i])
                                vWords[vCurrentIndexs[0]] < n.vWords[vCurrentIndexs[0]]; // Not equal
                        }
                    }
                }
            }


            return  vWords[vCurrentIndexs[0]] < n.vWords[vCurrentIndexs[0]];

        }
    }
};


vector<string> SplitString(const string &strInput, char cDelimiter, bool bSkipEmpty)
{
    vector<string> vRetValue;

    stringstream ss(strInput);  
    string strItem;
    while(std::getline(ss, strItem, cDelimiter))    
    {   
        // Skip Empty
        if(bSkipEmpty && strItem.size()==0)     
            continue;

        vRetValue.push_back(strItem);
    }

    return vRetValue;
}



void main()
{

// To Test
    vector<string> vInput;
    vInput.push_back("Connection to 11.22.33.44 port 3940 timed out client 1.2.3.4 source port 3940");
    vInput.push_back("Error loading page somepage.php by client 2.3.4.5");
    vInput.push_back("Load of page someotherpage.php by client 2.3.4.8 failed due to error 4930");
    vInput.push_back("Connection to 11.22.33.55 port 3829 timed out client 1.2.3.6 source port 3944");
    vInput.push_back("Load of page alt.php by client 2.3.4.92 failed due to error 3829");
    vInput.push_back("Load of page alt2.php by client 2.3.4.95 failed due to error 3829");


    set<structOneRecord> sRecords;

    for(int i=0; i<vInput.size(); i++)
    {
        vector<string> vWords = CMkDevStringUtilities::SplitString(vInput[i], ' ', true);

        structOneRecord stRecord;
        stRecord.vWords.resize(vWords.size());

        for(int j=0; j<vWords.size(); j++)
        {
            map<string, int>::iterator mIte = mStringToInt.find(vWords[j]);
            if(mIte == mStringToInt.end())                          
                mIte = mStringToInt.insert(mStringToInt.begin(), make_pair(vWords[j], mStringToInt.size()));            

            stRecord.vWords[j] = mIte->second;
        }


        set<structOneRecord>::iterator sIte = sRecords.find(stRecord);
        if(sIte != sRecords.end())
        {
            sIte->vLines.push_back(stRecord.vWords);
            if(sIte->vIndexOfMutableWords.size() == 0)
            {
                // Count diferences     
                vector<int> vCurrentIndexs;         
                for(int i=0; i<stRecord.vWords.size(); i++)
                {
                    if(sIte->vWords[i] != stRecord.vWords[i])                               
                        vCurrentIndexs.push_back(i);                                    
                }

                sIte->vIndexOfMutableWords = vCurrentIndexs;
            }
        }
        else    
        {
            stRecord.vLines.push_back(stRecord.vWords);
            sRecords.insert(stRecord);          
        }
    }
}

Это даст вам вывод, который можно легко распечатать как вывод, восстановив для каждой записи строку с подстроками, указанными в vWords (и заменив строки в индексах в изменяемых словах на «%%») и также может дать вам строки, упорядоченные по записи «type».

* Редактировать Забыл упомянуть, что в каждом structOneRecord vLines.size () подсчитывает количество ошибок.

Answer 8

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

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

similars = get_similar_strings( input_string, max_distance );
for each similar in similars do
   if is string then
     //construct template from string
   else
     // increase count
 done

Answer 9

Из вашего недавнего редактирования кажется, что вы сравниваете строки при выполнении пересечений.Не сравнивайте строки;просто сравните хэши.Вероятность того, что 64-битный хэш столкнется, в основном равна нулюЭто ускорит ваше сравнение строк, сэкономив вам много, много пропусков кэша.

Answer 10

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