Словарь / дерево быстрого поиска на основе поиска

Question

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

.biz stackru.com ru.wikipedia.com

Я хотел бы выполнить быстрый поиск, чтобы увидеть, соответствуют ли входные URL-адреса любому из этих 20000. Я мог бы использовать ключ словаря или HashSet.Contains, но он подходит только для точных совпадений. Поскольку база данных также содержит имена доменов верхнего уровня, я бы хотел, чтобы файл acmeycompany.biz также возвращался как совпадающий из-за домена верхнего уровня.biz. С другой стороны, fr.wikipedia.com не должен совпадать, поскольку поддомен отличается.

Простой цикл по списку и сравнение на основе строк также не вариант. Если у меня есть 1000 URL для сравнения, это просто слишком медленно. Так что это должен быть поиск по индексу на основе ключа.

Я думал о построении древовидной структуры, как показано ниже, а затем выполнял поиск на основе ключей, например:

.com.wikipedia.ru.stackru.biz

Затем я могу разделить входной URL-адрес (sampledomain.com) на части и выполнить поиск следующим образом.com -> .sampledomain

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

Спасибо!

Вот как я начал... Это код vb.net, но вы поняли идею.

 Public Class TreeNode

    Sub New()
        ChildNodes = New Dictionary(Of String, TreeNode)
    End Sub

    Public Property Key As String
    Public Property ChildNodes As Dictionary(Of String, TreeNode)

End Class

Private Tree As New Dictionary(Of String, TreeNode)

Sub BuildTree()

    For Each Link In Links

        If Uri.IsWellFormedUriString(Link, UriKind.Absolute) Then

            Dim Url As New Uri(Link)
            Dim Domain As String

            If Url.HostNameType = UriHostNameType.Dns Then

                Domain = Url.Host.ToLower.Replace("www.", "")

                Dim DomainParts() As String = Domain.Split(CChar("."))

                'lets start from TLD
                For Each Key In DomainParts.Reverse

                    'dont konw how to populate tree

                Next

            End If

        End If

    Next

End Sub

Function TreeLookup(Link As String) As Boolean

    Dim Url As New Uri(Link)
    Dim Domain As String
    Dim IsMatch As Boolean = False

    If Url.HostNameType = UriHostNameType.Dns Then

        Domain = Url.Host.ToLower.Replace("www.", "")

        Dim DomainParts() As String = Domain.Split(CChar("."))
        Dim DomainPartsCount As Integer = DomainParts.Length
        Dim Index As Integer = 0


        For Each Key In DomainParts

            Index += 1

            'use recursive loop to see if 

            'returns true if directory contains key and we have reached to the last part of the domain name
            If Index = DomainPartsCount Then

                IsMatch = True
                Exit For

            End If

        Next

    End If

    Return IsMatch

End Function

Answer 1

Вы можете создать словарь словарей хэш-карт. Первый словарь может содержать все записи ДВУ в паре со словарем всех доменов второго уровня, имеющих этот ДВУ. Тогда каждый домен второго уровня может содержать хэш-карту всех доменов нижнего уровня, которые он содержит. У каждой записи также будет флаг, указывающий, действительно ли эта запись находится в базе данных или просто заполнитель для записей более низкого уровня. Как и в коротком списке, который вы использовали, .com на самом деле отсутствует в списке, но все равно будет записью в ДВУ, поэтому предоставьте доступ к stackru.com а также wikipedia.com (который сам по себе будет заполнителем для ru.wikipedia.com). Затем поиск будет начинаться с TLD URL-адресов, затем со второго и, наконец, более низкого уровня, если необходимо углубиться.

Надеюсь, я правильно понял вашу дилемму и адекватно объяснил свою идею.

Редактировать: самый низкий уровень должен быть только хэш-картой.

---

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

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

// TLD, SLD and LLD are the three levels of the current domain you are adding into the tree
if Tree does not contain the TLD
    Add TLD to the Tree with a new TreeNode

if SLD does not exist for the current domain
    Mark the Tree at TLD as a match
else   
    if Tree[TLD] does not contain the SLD
        Add SLD to the Tree[TLD] Node

    if LLD does not exist for the current domain
        Mark the Tree[TLD] at SLD as a match
    else   
        if Tree[TLD][SLD] does not contain the LLD
            Add LLD to the Tree[TLD][SLD] Node
            // Don't really need to mark the node
            // as every LLD would be a match
            // Probably would need to mark if made recursive

Чтобы найти домен (опять же, можно сделать рекурсивным):

// TLD, SLD and LLD are for the domain you looking for
if Tree does not contain TLD
    you are done, no match
else
    if Tree[TLD] is marked
        done, match
    else
        if Tree[TLD] does not contain SLD
            done, no match
        else
            if Tree[TLD][SLD] is marked
                done, match
            else
                if Tree[TLD][SLD] contains LLD
                    done, match
                    // would need to check if the node
                    // is marked if made recursive

Answer 2

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

create table MyList
(
    [TLD] nvarchar(10) not null,
    [Domain] nvarchar(50) not null,
    [Subdomain] nvarchar(50) not null,

    unique ([TLD], [Domain], [Subdomain]) 
    --this means that you can't add the same data twice
)

Теперь используйте SQL, чтобы получить нужные данные.

select *
from MyList
where [TDL] = '.com'

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

Что касается причины для таблицы, прочитайте о нормализации базы данных

Вам нужно будет выполнить какое-то преобразование данных, если вы храните свои URL-адреса только в одном столбце.