Найти общий шаблон среди набора URL-адресов

Question

У меня есть файл с URL-адресами. Файл выглядит следующим образом

http://www.example.com/images/1 
http://www.example.com/images/2 
. 
. 
. 
http://www.example.com/images/2000 
http://www.example.org/p/q/r/1/s/t 
http://www.example.org/p/q/r/2/s/t 
http://www.example.org/p/q/r/3/s/t 
. 
. 
. 
http://www.example.org/p/q/r/5000/s/t 

и так далее. URL-адреса не сортируются. Я просто разобрался, чтобы объяснить это четко.

Я должен обработать эти URL, таким образом, что если есть одно слово (слово между 2 косой чертой) отличаются от 2 URL, и числа таких случаев составляет> 1000, я заменить это слово на *

К примеру, в выше файл, у меня будет

http://www.example.com/images/* 
http://www.example.org/p/q/r/*/s/t 

размер файла в сотни гигабит. Может ли кто-нибудь помочь мне с этим?

Answer 1

Мы предложили алгоритм MapReduce для этой проблемы в this paper (конец страницы 3), который представляет собой параллельную адаптацию последовательного алгоритма извлечения инфикса, введенного в another paper (стр. 4, Алгоритм 1).

Здесь я привожу последовательный алгоритм:

1. sort URIs 
2. tokenize URIs at all special characters 
3. cluster URIs according to the first n tokens 
4. for all clusters do 
5. for all URIs in the cluster do 
6.  for all possible prefixes do 
7.  find the set of (distinct) next tokens T 
8.  end for 
9. end for 
10. for all URIs in the cluster do 
11.  set as a prefix the one with the largest |T| 
12.  set as infix the substring following the prefix 
13. end for 
14. end for 

Основная идея параллельной версии является то, что вы создаете кластеры (шаг 3), используя в качестве выходной карты ключа второго токена URI (после http: //), а затем выполните аналогичные операции с шагами 4-14) в каждом редукторе, то есть в каждом кластере. Исходный код нашей параллельной версии можно найти here.

После того, как вы выберете «инфикс» каждого URI, вы можете легко заменить его любым желаемым персонажем, например '*'. Имейте в виду, что это дорогостоящий процесс, который имеет смысл делать в MapReduce, только когда у вас есть миллионы + URI, которые, по-видимому, у вас есть.