Функция N-граммы в vb.net -> создавать граммы для слов вместо символов - PullRequest
Новая
       15

Функция N-граммы в vb.net -> создавать граммы для слов вместо символов

2 голосов
/ 10 марта 2010

Я недавно узнал о n-граммах и классной возможности сравнивать с ним частоту фраз в текстовом теле. Сейчас я пытаюсь создать приложение vb.net, которое просто получает текстовое тело и возвращает список наиболее часто используемых фраз (где n> = 2).

Я нашел C # пример того, как генерировать n-грамм из текстового тела, поэтому я начал с преобразования кода в VB. Проблема в том, что этот код создает один грамм на символ вместо одного на слово. Разделители, которые я хочу использовать для слов: VbCrLf (новая строка), vbTab (вкладки) и следующие символы:! @ # $% ^ & * () _ + - = {} | \: \ "'? ¿ /.,<>'¡º×÷';«»[]

Кто-нибудь знает, как я могу переписать следующую функцию для этой цели: 

   Friend Shared Function GenerateNGrams(ByVal text As String, ByVal gramLength As Integer) As String()
    If text Is Nothing OrElse text.Length = 0 Then
        Return Nothing
    End If

    Dim grams As New ArrayList()
    Dim length As Integer = text.Length
    If length < gramLength Then
        Dim gram As String
        For i As Integer = 1 To length
            gram = text.Substring(0, (i) - (0))
            If grams.IndexOf(gram) = -1 Then
                grams.Add(gram)
            End If
        Next

        gram = text.Substring(length - 1, (length) - (length - 1))
        If grams.IndexOf(gram) = -1 Then
            grams.Add(gram)

        End If
    Else
        For i As Integer = 1 To gramLength - 1
            Dim gram As String = text.Substring(0, (i) - (0))
            If grams.IndexOf(gram) = -1 Then
                grams.Add(gram)

            End If
        Next

        For i As Integer = 0 To (length - gramLength)
            Dim gram As String = text.Substring(i, (i + gramLength) - (i))
            If grams.IndexOf(gram) = -1 Then
                grams.Add(gram)
            End If
        Next

        For i As Integer = (length - gramLength) + 1 To length - 1
            Dim gram As String = text.Substring(i, (length) - (i))
            If grams.IndexOf(gram) = -1 Then
                grams.Add(gram)
            End If
        Next
    End If
    Return Tokeniser.ArrayListToArray(grams)
End Function

Ответы [ 2 ]

2 голосов
/ 10 марта 2010

n -грамма для слов - это просто список длиной n , в котором хранятся эти слова. Список n -грамм - это просто список слов. Если вы хотите сохранить частоту, вам нужен словарь, который проиндексирован этими n -граммами. Для вашего особого случая 2 грамма вы можете представить себе что-то вроде этого: 

Dim frequencies As New Dictionary(Of String(), Integer)(New ArrayComparer(Of String)())
Const separators as String = "!@#$%^&*()_+-={}|\:""'?¿/.,<>’¡º×÷‘;«»[] " & _
                             ControlChars.CrLf & ControlChars.Tab
Dim words = text.Split(separators.ToCharArray(), StringSplitOptions.RemoveEmptyEntries)

For i As Integer = 0 To words.Length - 2
    Dim ngram = New String() { words(i), words(i + 1) }
    Dim oldValue As Integer = 0
    frequencies.TryGetValue(ngram, oldValue)
    frequencies(ngram) = oldValue + 1
Next

frequencies теперь должен содержать словарь со всеми двумя последовательными парами слов, содержащимися в тексте, и частотой, с которой они появляются (как последовательная пара).

Для этого кода требуется класс ArrayComparer: 

Public Class ArrayComparer(Of T)
    Implements IEqualityComparer(Of T())

    Private ReadOnly comparer As IEqualityComparer(Of T)

    Public Sub New()
        Me.New(EqualityComparer(Of T).Default)
    End Sub

    Public Sub New(ByVal comparer As IEqualityComparer(Of T))
        Me.comparer = comparer
    End Sub

    Public Overloads Function Equals(ByVal a As T(), ByVal b As T()) As Boolean _
            Implements IEqualityComparer(Of T()).Equals
        System.Diagnostics.Debug.Assert(a.Length = b.Length)
        For i As Integer = 0 to a.Length - 1
            If Not comparer.Equals(a(i), b(i)) Then Return False
        Next

        Return True
    End Function

    Public Overloads Function GetHashCode(ByVal arr As T()) As Integer _
            Implements IEqualityComparer(Of T()).GetHashCode
        Dim hashCode As Integer = 17
        For Each obj As T In arr
            hashCode = ((hashCode << 5) - 1) Xor comparer.GetHashCode(obj)
        Next

        Return hashCode
    End Function
End Class

К сожалению, этот код не компилируется в Mono, поскольку у компилятора VB возникают проблемы с поиском универсального класса EqualityComparer. Поэтому я не могу проверить, правильно ли работает реализация GetHashCode, но все должно быть в порядке.

0 голосов
/ 11 марта 2010

Большое спасибо Конраду за начало решения!

Я попробовал ваш код и получил следующий результат: 

Text = "Hello I am a test Also I am a test"
(I also included whitespace as a separator)

frequencies now has 9 items:
---------------------
Keys: "Hello", "I"
Value: 1
---------------------
Keys: "I", "am"
Value: 1
---------------------
Keys: "am", "a"
Value: 1
---------------------
Keys: "a", "test"
Value: 1
---------------------
Keys: "test", "Also"
Value: 1
---------------------
Keys: "Also", "I"
Value: 1
---------------------
Keys: "I", "am"
Value: 1
---------------------
Keys: "am", "a"
Value: 1
---------------------
Keys: "a", "test"
Value: 1
---------------------

Мой первый вопрос: не должны ли 3 последние пары ключей получить значение 2, поскольку они встречаются в тексте два раза?

Второе: причина, по которой я попал в n-граммный подход, заключается в том, что я не хочу ограничивать количество слов (n) определенной длиной. Есть ли способ создать динамический подход, который сначала пытается найти соответствие самой длинной фразы, а затем перейти к последнему количеству слов в 2?

Моя цель для приведенного выше примера запроса: 

---------------------
Match: "I am a test"
Frequency: 2
---------------------
Match: "I am a"
Frequency: 2
---------------------
Match: "am a test"
Frequency: 2
---------------------
Match: "I am"
Frequency: 2
---------------------
Match: "am a"
Frequency: 2
---------------------
Match: "a test"
Frequency: 2
---------------------

Для этого существует аналогичный подход C ++, написанный Хатемом Мостафой на codeproject.com: Алгоритм N-граммы и быстрого извлечения паттерна

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

...