Учитывая большой список URL-адресов, каков наилучший метод интеллектуального анализа данных для группировки URL-адресов по шаблонам или regEx?

Question

У меня есть список из 1 миллиона URL-адресов, и я хотел бы объединить похожие URL-адреса. Результатом процесса будет список регулярных выражений или шаблонов. В идеале я хотел бы использовать Ruby для получения данных. Мои первоначальные мысли направлены на использование классификатора машинного обучения, но я не уверен, с чего начать или какой метод анализа данных использовать.

Возможный пример:

Введите:

http://www.example.com/folder-A/file.html
http://www.example.com/folder-A/dude.html
http://www.example.com/folder-B/huh.html
http://www.example.com/folder-C/what-ever.html

Выход:

http://www\.example\.com/folder-A/[a-z]\.html
http://www\.example\.com/folder-[A-C]/[-a-z]\.html

Answer 1

Эта программа:

#!/usr/bin/env perl

use strict;
use warnings;

# the following is a CPAN module requiring independent installation:
use Regexp::Assemble;

my @url_list = qw(
    http://www.example.com/folder-A/file.html
    http://www.example.com/folder-A/dude.html
    http://www.example.com/folder-B/huh.html
    http://www.example.com/folder-C/what-ever.html
);

my $asm = Regexp::Assemble->new;
for my $url (@url_list) {
    $asm->add($url);
}

my $pat = $asm->re;
for ($pat) {
    s/^.*?://;
    s/\)$//;
}

print "$pat\n";

при запуске должным образом распечатывает:

http://www.example.com/folder-(?:A/(?:dud|fil)e|C/what-ever|B/huh).html

Это то, что вы искали?

Answer 2

Привет, вы можете использовать эту (http://www.brics.dk/automaton/) библиотеку автоматов для создания или работы нескольких строк, а затем оптимизировать автомат. В этом случае вы просто получите обобщенное одно регулярное выражение.

Более простое решение - использовать оптимизацию префикса для извлечения аналогичной первой части, для этого взгляда на этот пример http://code.google.com/p/graph-expression/wiki/RegexpOptimization.

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

Answer 3

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

Answer 4

Если вы спрашиваете, как вам следует проанализировать URL-адрес с помощью регулярного выражения, взгляните на RFC 2396 .

IETF.

RFC 2396 Универсальный синтаксис URI Август 1998

B. Разбор ссылки на URI с помощью регулярного выражения

Как описано в разделе 4.3, общий синтаксис URI не достаточно для устранения неоднозначности компонентов некоторых форм URI. Поскольку описанный в этом разделе «жадный алгоритм» идентичен к методу устранения неоднозначности, используемому регулярными выражениями POSIX, он Естественно и обычно используется регулярное выражение для разбора потенциальные четыре компонента и идентификатор фрагмента URI ссылка. * * +1010

Следующая строка - это регулярное выражение для разбиения Ссылка URI на его компоненты.

  ^(([^:/?#]+):)?(//([^/?#]*))?([^?#]*)(\?([^#]*))?(#(.*))?
   12            3  4          5       6  7        8 9

Цифры во второй строке выше служат только для помощи читаемость; они указывают ориентиры для каждого подвыражение (то есть каждая парная скобка). Мы ссылаемся на значение для подвыражения соответствует $. Например, соответствие приведенное выше выражение для

  http://www.ics.uci.edu/pub/ietf/uri/#Related

приводит к следующим совпадениям подвыражения:

  $1 = http:
  $2 = http
  $3 = //www.ics.uci.edu
  $4 = www.ics.uci.edu
  $5 = /pub/ietf/uri/
  $6 = <undefined>
  $7 = <undefined>
  $8 = #Related
  $9 = Related

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

  scheme    = $2
  authority = $4
  path      = $5
  query     = $7
  fragment  = $9

и, двигаясь в противоположном направлении, мы можем воссоздать URI ссылка из его компонентов с использованием алгоритма в шаге 7 Раздел 5.2.

Оттуда вы сможете сравнивать фрагменты URL и определять шаблоны.