У меня есть строки большого размера (XXM-XXXM), которые выглядят как (маленький образец):
Я не имею ни малейшего представления о всех возможных строках ошибки, ни о перестановках. Я хочу сгруппировать все подобные ошибки вместе и создать статистические данные, показывающие количество ошибок для каждой группы строк ошибок.
Итак, по сути, я хотел бы сгруппировать наиболее похожие строки вместе, а строки могут принадлежать нескольким группам.
Спасибо!
Отказ от ответственности: я никогда раньше не решал такую проблему.
Я могу подумать о нескольких способах думать о вашей проблеме:
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()
Если вы запустите его на своих основных данных, вы должны получить несколько кластеров. Примечание: измените код, чтобы записать кластеры для разделения файлов. Я думаю, вы захотите снова запустить кластеры через код, рекурсивно, пока не найдете интересующие вас подмножества.
Что бы я сделал здесь, это написать распознаватель параметров. Это распознает следующие подстроки (когда они окружены пробелами) в качестве параметров:
Нет сомнений, что будет больше, но список не должен становиться слишком большим. Затем вы заменяете каждый параметр держателем места:% d,% url,% phpfile. Теперь вы можете просто отсортировать строки.
Вы можете найти непризнанные типы параметров, просмотрев строки вывода, которые происходят редко. Например, если есть тип параметра h: m: s для времени суток, строки, содержащие этот незадержанный параметр, будут уникальными или почти такими, и вы можете найти этот новый тип параметра, просто просматривая список из 100 или так что "почти уникальные" строки. Затем добавьте h: m: s в свой список, замените все такие вхождения на% времени и запустите его снова.
Прочитав еще несколько страниц из CRM114 Контролируемый регулярный мутилятор:
Спам - большая цель с CRM114, но это не специализированный инструмент для электронной почты. CRM114 используется для сортировки веб-страниц, резюме, записей в блогах, файлов журналов и множества других вещей. Точность может достигать 99,9%. Другими словами, CRM114 учится, и он быстро учится.
Это может быть, короче, именно то, что вам нужно. И вы можете рассчитывать на его оптимизацию.
Интересный вопрос... Просто спонтанная идея, которую можно закодировать довольно быстро:
Производительность (очень приблизительная оценка): в 1. фазе достаточно пробовать ваши данные, в 2. фазе вам необходимо последовательно обрабатывать каждую строку, поэтому вы находитесь в пределах O (n), где n - количество строк в вашем наборе данных (используйте хэш-карту для O (1) вставить в 1. фазу и O (1) тест в 2. фазе). Потребление памяти зависит от количества различных слов (1. фаза) и различных предложений (2. фаза). Если у вас есть большая вариация слов, словарь для подсчета вхождений на первом этапе может стать проблематичным.
В Python в качестве структур данных я бы попробовал со специальным (перформативным) типом данных типа Counter.
Хорошо, я думаю, что идея сравнения выходит за рамки этой проблемы. даже сравнение значения хеша/сопоставления требует много времени. поэтому может быть возможным использование bucketing на основе отображения сообщения об ошибке (строка), а затем проверка может быть возможным.
для этого вам нужно найти какую-то идею для сопоставления отдельной строки (ее просто обратная техника хэширования, которая больше подчеркивает необходимость избегать конфликтов), но я думаю, что здесь столкновений почти для одной и той же строки в порядке. поэтому функция отображения должна быть функцией позиционного свойства алфавитов, длины строки.
когда выполняется сопоставление, мы создаем ведро с диапазоном значений 1: (0-10) (или как это по значению) группа 2: (10-20)..... и так далее... так как мы сказали, что аналогичная строка должна иметь аналогичное значение, аналогичная строка помещается в один и тот же ковш
поэтому всякий раз, когда встречается новое сообщение, мы сопоставляем его с числовым эквивалентом и помещаем в подходящее ведро.
Очень сложно ответить без каких-либо предположений о вводе.
Мой подход:
Только вы можете указать (без предположений), если хотите группировать определенный набор "похожих" строк или нет. Должно быть конечное количество типов сообщений об ошибках, поэтому после нескольких итераций это должно дать достаточно хороший результат.
Другим подходом может быть, исходя из предположения, что сходство основано на числах и IP-адресах в строках, заключается в их поиске и использовании этих чисел для классификации элементов. Это опять же связано с более конкретным описанием ваших правил, но может избавить вас от повторного создания правил (если предположение действительно действительно).
Можно было бы подумать о измерении levenshtein-distance между строками (или с использованием аналогичного алгоритма), но для классификации, которая потребовала бы слишком много шагов.
Хм, зачем изобретать колесо - посмотрите бесплатную версию splunk, она предназначена для такого рода задачи.
Если бы это зависело от меня, я бы использовал python и регулярные выражения. Отказ от ответственности: я никогда не использовал python в том масштабе, о котором вы говорите.
Вот первые два элемента из вашего образца вывода, переписанные в виде регулярных выражений:
Не так плохо, не так ли? Вы можете использовать их как "ключи" для ваших кодов верхнего уровня.
Тогда ваш код для сопоставления заданной строки (ов) с ведром становится невероятно простым:
for bucket in buckets:
if re.match(bucket.regex, s):
bucket.matchingStrings.append(s)
break
# else if no buckets match, generate a new bucket/regex for s
Создание этих регулярных выражений будет сложной частью. Вам нужно иметь правила для выбора частей строки, которые необходимо обобщить. В вашем случае общие части кажутся номерами, IP-адресами и именами файлов. Вам нужно будет придумать правильные выражения для каждого сценария, но здесь простая подстановка, которая заменяет числа в строке шаблоном регулярного выражения, представляющим число.
pattern = r"\d+"
re.sub(pattern, pattern, "Failed to count from 0 to 600")
# returns r"Failed to count from \d+ to \d+"
Бьюсь об заклад, вы получите довольно далеко с заменой \d + и не более того.
Не алгоритмическое решение само по себе, но может пригодиться и предоставить вам еще большую свободу с точки зрения вычислительной сложности: анализ файлов журналов является одним из основных вариантов реализации MapReduce Hadoop и его друзей. Поэтому, если у вас проблемы с масштабируемостью, вы можете начать думать о решении проблемы на управляемом подмножестве (шаг карты), а затем объединить вывод подмножеств в один (шаг уменьшения). Например, вы можете найти ведра в подмножествах, затем сравнить все наборы ведер и объединить похожие.
Из вашего недавнего редактирования кажется, что вы сравниваете строки при выполнении перекрестков. Не сравнивайте строки; просто сравните хеши. Вероятность столкновения 64-битного хэша в основном равна нулю. Это ускорит время сравнения строк, сохранив много промахов в кэше.
Я сделал что-то довольно похожее, где мне нужно найти похожие строки из базы данных. Trie с некоторыми дополнениями поможет вам в этом. Общие реализации попыток просто поддерживают вставку и префикс поиска/поиска. Однако можно также рассчитать расстояние Levensthein до всех данных в trie, а затем использовать его для получения ближайших строк.
Алгоритм Levensthein, реализованный в trie, также может использоваться для определения того, что изменилось между двумя строками и создать шаблон. Что-то вроде этого:
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
Я бы сделал что-то вроде этого.
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 (и заменяя строки в индексах в Mutable words на "%%" ) и также может дать вам строки, упорядоченные по типу записи.
* Редактировать Забыл упомянуть, что под каждым structOneRecord vLines.size() дает вам счетчик ошибок.
Я думаю, что потребуется какое-то ручное вмешательство, и наилучшим подходом будет подсчет частоты.