Тенденции в Твиттере: объедините разные варианты написания

Question

Тенденции Твиттера часто состоят из нескольких слов. Но для составных терминов часто существуют разные способы написания, например ::100100

«Принц-полукровка» / «Принц-полукровка»

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

У вас есть название темы слева и различные варианты написания справа. Как вы думаете, это делается вручную или автоматически? Возможно ли сделать это автоматически? Если да: как?

Надеюсь, вы мне поможете. Заранее спасибо!

Answer 1

Что вам в основном нужно, так это найти сходство между двумя строками .

Я думаю, алгоритм Soundex - это то, что вы ищете. Его можно использовать для сравнения строк в зависимости от их звучания. Или как вики описывает:

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

И

Используя этот алгоритм [РЕДАКТИРОВАТЬ: т. Е. «Оценивать» слова по букве и трем цифрам], и «Роберт», и «Руперт» возвращают одну и ту же строку «R163», а «Рубин» выдает «R150». "Ashcraft" дает "A261".

Там также расстояние Левенштейна .

Удачи.

Answer 2

Я постараюсь ответить на свой вопрос, основываясь на комментарии Broken Link (спасибо за это):

---

Вы извлекли фразы, содержащие от 1 до 3 слов, из вашей базы данных документов. Среди этих выделенных фраз есть следующие фразы:

• Принц-полукровка
• Принц-полукровка
• Принц-полукровка

Для каждой фразы вы убираете все специальные символы и пробелы и делаете строку строчной:

$ фраза = 'Принц-полукровка'; $ фраза = preg_replace ('/ [^ a-z] / i', '', $ фраза); $ фраза = strtolower ($ фраза); // результат - "полукровка"

Когда вы это сделаете, все 3 фразы (см. Выше) имеют одно общее написание:

• Принц-полукровка => Принц-полукровка
• Принц-полукровка => Принц-полукровка
• Принц-полукровка => Принц-полукровка

Так что "полукровка Принц" - родительская фраза. Вы вставляете в свою базу данных как обычную фразу, так и родительскую фразу.

Чтобы показать «Администратора популярных трендов», такого как Twitter, выполните следующие действия:

// first select the top 10 parent phrases
$sql1 = "SELECT parentPhrase, COUNT(*) as cnt FROM phrases GROUP BY parentPhrase ORDER BY cnt DESC LIMIT 0, 10";
$sql2 = mysql_query($sql1);
while ($sql3 = mysql_fetch_assoc($sql2)) {
    $parentPhrase = $sql3['parentPhrase'];
    $childPhrases = array(); // set up an array for the child phrases
    $fifthPart = round($sql3['cnt']*0.2);
    // now select all child phrases which make 20% of the parent phrase or more
    $sql4 = "SELECT phrase FROM phrases WHERE parentPhrase = '".$sql3['parentPhrase']."' GROUP BY phrase HAVING COUNT(*) >= ".$fifthPart;
    $sql5 = mysql_query($sql4);
    while ($sql6 = mysql_fetch_assoc($sql5)) {
        $childPhrases[] = $sql3['phrase'];
    }
    // now you have the parent phrase which is on the left side of the arrow in $parentPhrase
    // and all child phrases which are on the right side of the arrow in $childPhrases
}

Это то, о чем ты думал, Broken Link? Будет ли это работать?

Answer 3

Есть много способов сделать это. Одна прямолинейная статья о проверке стиля «Вы имели в виду» в Google хорошо читается, чтобы узнать, как этого добиться. Автор Питер Норвиг, директор по исследованиям в Google.

http://norvig.com/spell-correct.html

Answer 4

"anderstornvig" упомянул расстояние Левенштейна / редактирования, что является отличной идеей, но не совсем уместно, потому что некоторые перестановки более значимы, чем другие перестановки. Кажется, проблема в том, что мы используем много знаний, специфичных для предметной области, когда определяем, какие различия являются «существенными», а какие «незначительными». Например, мы знаем, что дефис в «Принце-полукровке» очень важен, но число в «Firefox 3» очень важно.

По этой причине вы можете подумать о настройке простой метрики, такой как Левенштейн. Добавьте параметры, позволяющие настроить, какие различия важны, а какие не важны.

В частности, Левенштейн подсчитывает количество «правок» (то есть вставок, удалений и подстановок), необходимых для превращения одной строки в другую. По сути, он взвешивает каждый редактор одинаково. Вы можете написать реализацию, которая по-разному взвешивает некоторые изменения. Например, изменение «-» на «» должно иметь очень низкий вес (что указывает на неважность). Изменение «3» на «2», когда число одно, должно иметь очень большой вес (что указывает на высокую важность).

Параметрируя расчет, вы создаете путь для постоянного улучшения вашего алгоритма. Создайте начальную конфигурацию и запустите ее на некоторых тестовых данных. Найдите места, где метрика слабая, например, где объединяются два термина, которые, по вашему мнению, должны быть разделены, и изменяйте параметризацию до тех пор, пока вы не будете удовлетворены.

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

Answer 5

Скорее всего, у них есть некоторые автоматические системы, которые предлагают вероятных кандидатов на объединение, и тогда человек делает окончательный выбор объединить их. Там могут быть некоторые они объединяются автоматически.

• Ваше предложение об удалении пробелов и других знаков препинания является хорошим. Скорее всего, они автоматически комбинируют вещи, отличающиеся только пунктуацией или пробелами.
• Множественное число против единственного числа: поиск этих различий будет легко автоматизировать и даст вероятных кандидатов на объединение.
• Распространенные орфографические ошибки - есть базы данных по орфографическим ошибкам. Они могут даже полагаться на Google API для написания предложений (я думаю, что они раскрывают это).
• Soundex (или аналогичный) хорош для поиска орфографических ошибок, но сначала нужно пройти через два вышеупомянутых фильтра (удалить пробелы, знаки препинания и множественное число), а затем, скорее всего, нужен человек сделать звонок, если они одинаковы. Но если бы вы могли представить графическое представление, показывающее кластеризацию с таким же или похожим soundex, то вы действительно упростили бы эту часть. Вы можете автоматически отправлять уведомление, когда кластер начинает появляться и отображать тенденции (в любом случае они действительно заботятся только о трендовых темах, поэтому, если даже объединенный кластер не имеет тенденций, они могут подождать, чтобы изучить его).

Где вам действительно нужно, чтобы вмешался человек, когда есть общие прозвища. Как Майкл Джексон, MJ, Майкл и т. Д. Или MacDonalds, McD, Micky-D и т. Д. А затем с техническим у вас есть Visual Studio, VS2008, VS и т. Д. Или StackOverflow, SO и т. Д. Затем C #, C-Sharp, C # .NET все одинаковы, но C и C ++ разные.

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

Answer 6

Предполагая, что трендовые темы генерируются вычислительно, точный алгоритм, делающий это в Твиттере, будет трудно угадать. Скорее всего, он очень конфиденциальный и запатентованный (как бы страшно это ни звучало для патентных алгоритмов).

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

Очевидное полезное чтение на эту тему из вики:

• Обработка естественного языка

Удачи.

Answer 7

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