Как я могу обнаружить общие подстроки в списке строк
Атрибут по-прежнему является сложным элементом в соответствии с DOM (имеет пространство имен и т. д.). Использование:
//table[php:function('preg_match', '/post\d+/', string(@id))]
Теперь нам нужно логическое возвращение, так что:
function booleanPregMatch($match,$string){
return preg_match($match,$string)>0;
}
$xpath->registerPHPFunctions();
foreach($xpath->query("//table[@id and php:function('booleanPregMatch', '/post\d+/', string(@id))]") as $key => $row){
echo $row->ownerDocument->saveXML($row);
}
BTW: для более сложных вопросов вы можете, конечно, скрытно проверить, что происходит с этим:
//table[php:function('var_dump',@id)]
Жаль, что у нас нет доступных функций XPATH 2.0, но если вы можете справиться с этим требованием с более ненадежным starts-with, я всегда предпочел бы, что над импортом функций PHP.
4 ответа
Я бы начал здесь: http://en.wikipedia.org/wiki/Longest_common_substring_problem
Во внешних ссылках есть ссылки на дополнительную информацию, включая Perl-реализации два алгоритма, описанные в статье.
Отредактировано для добавления:
Основываясь на обсуждении, я все еще думаю, что самая длинная общая подстрока может быть в основе этой проблемы. Даже в примере журнала, на который вы ссылаетесь в своем комментарии, определяющей характеристикой этого набора является подстрока «Журнал».
Сначала я хотел бы рассмотреть, что определяет набор как отдельный от других наборов. Это дает вам ваш раздел для разделения данных, и тогда проблема заключается в том, чтобы измерить, насколько общность существует в наборе. Если определяющей характеристикой является общая подстрока, тогда самая длинная общая подстрока будет логической отправной точкой.
Для автоматизации процесса обнаружения множеств, как правило, вам понадобится попарная мера общности, которую вы можете использовать для измерения «разницы» между всеми возможными парами. Затем вам нужен алгоритм для вычисления раздела, который дает наименьшую общую разницу. Если мера разницы не является самой длинной общей подстрокой, это нормально, но тогда вам нужно определить, какой она будет. Очевидно, это должно быть что-то конкретное, что вы можете измерить.
Имейте в виду также, что свойства вашего измерения разницы будут влиять на алгоритмы, которые могут быть использованы для создания раздела. Например, предположим, что diff (X, Y) дает меру разницы между X и Y. Тогда, вероятно, было бы полезно, если бы ваша мера расстояния была такой, что diff (A, C) < = diff (A, B) + diff (B, C). И очевидно, что diff (A, C) должен быть таким же, как diff (C, A).
Размышляя об этом, я также начинаю задаваться вопросом, можем ли мы представить себе «различие» как расстояние между любыми двумя строками, и, строго определив расстояние, не могли бы мы затем попытаться выполнить какой-нибудь кластерный анализ входных строк. Просто мысль.
Для этого конкретного примера строк, чтобы сделать его предельно простым, рассмотрите возможность использования простого разделения слова / цифры.
Нецифровая последовательность, очевидно, может начинаться с заглавной буквы (целая). После разбивки всех строк на группы последовательностей, что-то вроде
[Entire][S][1]
[Entire][S][2]
[J][27][Red][P][1]
[J][27][Green][P][1]
[J][27][Red][P][2]
....
[Journal][P][1][Blue]
[Journal][P][1][Green]
Затем начните группировку по группам, вы довольно скоро увидите, что префикс «Весь» является общим для некоторой группы и что все подгруппы имеют S в качестве головной группы, поэтому переменная только для тех равно 1,2. Для случая J27 вы можете видеть, что J27 является только листом, но затем он разветвляется на красный и зеленый.
Так что некоторый вид структуры List
Существует множество подходов к схожести строк. Я бы посоветовал взглянуть на эту библиотеку с открытым исходным кодом, которая реализует множество метрик, таких как расстояние Левенштейна.
Что-то вроде этого может сработать.
- Создайте дерево, которое представляет все ваши строки.
В приведенном вами примере будет два ребра от корня: «E» и «J». Затем ветвь «J» будет разделена на «Jo» и «J2».
Одна ветвь, которая разветвляется, например, WholeS- (разветвляется на 1, 2) указывает на выбор, так что это будет CompleteS [1,2]
Если нить «слишком коротка» по отношению к вилке, например BA- (разветвляется на NANA и HAMAS), мы указываем два слова («банан, багамы»), а не выбор («ba [nana, hamas ] "). «Слишком короткий» может быть таким же простым, как «если часть после разветвления длиннее, чем часть до», или может быть взвешено по количеству слов с заданным префиксом.
Если два поддерева являются » CDGreen, вы можете обнаружить, что поддерево с корнем в "AB" такое же, как поддерево с корнем в "CD", поэтому вы должны объединить их. В вашем выводе это будет выглядеть так: [левая ветвь, правая ветвь] [поддерево], поэтому: [AB, CD] [Красный, Синий, Зеленый]. Что делать с близкими, но не совсем одинаковыми поддеревьями? Вероятно, нет однозначного ответа, но у кого-то здесь может быть хорошая идея.
Я отмечаю этот ответ вики сообщества. Не стесняйтесь расширять его, чтобы вместе мы могли получить разумный ответ на вопрос.
CDGreen, вы можете обнаружить, что поддерево с корнем в "AB" такое же, как поддерево с корнем в "CD", поэтому вы должны объединить их. В вашем выводе это будет выглядеть так: [левая ветвь, правая ветвь] [поддерево], поэтому: [AB, CD] [Красный, Синий, Зеленый]. Что делать с близкими, но не совсем одинаковыми поддеревьями? Вероятно, нет однозначного ответа, но у кого-то здесь может быть хорошая идея.Я отмечаю этот ответ вики сообщества. Не стесняйтесь расширять его, чтобы вместе мы могли получить разумный ответ на вопрос.
Что делать с близкими, но не совсем одинаковыми поддеревьями? Вероятно, нет однозначного ответа, но у кого-то здесь может быть хорошая идея.Я отмечаю этот ответ вики сообщества. Не стесняйтесь расширять его, чтобы вместе мы могли получить разумный ответ на вопрос.
Что делать с близкими, но не совсем одинаковыми поддеревьями? Вероятно, нет однозначного ответа, но у кого-то здесь может быть хорошая идея.Я отмечаю этот ответ вики сообщества. Не стесняйтесь расширять его, чтобы вместе мы могли получить разумный ответ на вопрос.