#text #split #mediawiki #categories
#текст #разделить #mediawiki #Категории
Вопрос:
Википедия использует «HTML sitemap» для ссылки на каждую отдельную страницу содержимого. Огромное количество страниц должно быть разбито на множество групп, чтобы на каждой странице было не более 100 ссылок, конечно.
Вот как это делает Википедия:
Весь список статей разделен на несколько больших групп, которые определяются их первым и последним словом каждая:
- от «Рейтинг ААА» до «ранний пользователь»
- от «земли» до «плача»
- от «низкого» до «священника»
- …
Когда вы нажимаете на одну категорию, этот диапазон (например, от «земля» до «плач») разделяется аналогичным образом. Эта процедура повторяется до тех пор, пока текущий диапазон не будет включать только около 100 статей, чтобы их можно было отобразить.
Мне очень нравится этот подход к спискам ссылок, который сводит к минимуму количество кликов, необходимых для доступа к любой статье.
Как вы можете создать такой список статей автоматически?
Итак, мой вопрос заключается в том, как можно автоматически создать такую индексную страницу, которая позволяет переходить к меньшим категориям, пока количество содержащихся статей не станет достаточно маленьким для их отображения.
Представьте, что задан массив всех названий статей, как бы вы начали программировать индекс с автоматическим разделением по категориям?
Array('AAA rating', 'abdicate', ..., 'zero', 'zoo')
Было бы здорово, если бы вы могли мне помочь. Конечно, мне не нужно идеальное решение, но полезный подход. Заранее большое вам спасибо!
Редактировать: теперь найдена часть в программном обеспечении Википедии (MediaWiki):
<?php
/**
* Implements Special:Allpages
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License along
* with this program; if not, write to the Free Software Foundation, Inc.,
* 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
* http://www.gnu.org/copyleft/gpl.html
*
* @file
* @ingroup SpecialPage
*/
/**
* Implements Special:Allpages
*
* @ingroup SpecialPage
*/
class SpecialAllpages extends IncludableSpecialPage {
/**
* Maximum number of pages to show on single subpage.
*/
protected $maxPerPage = 345;
/**
* Maximum number of pages to show on single index subpage.
*/
protected $maxLineCount = 100;
/**
* Maximum number of chars to show for an entry.
*/
protected $maxPageLength = 70;
/**
* Determines, which message describes the input field 'nsfrom'.
*/
protected $nsfromMsg = 'allpagesfrom';
function __construct( $name = 'Allpages' ){
parent::__construct( $name );
}
/**
* Entry point : initialise variables and call subfunctions.
*
* @param $par String: becomes "FOO" when called like Special:Allpages/FOO (default NULL)
*/
function execute( $par ) {
global $wgRequest, $wgOut, $wgContLang;
$this->setHeaders();
$this->outputHeader();
$wgOut->allowClickjacking();
# GET values
$from = $wgRequest->getVal( 'from', null );
$to = $wgRequest->getVal( 'to', null );
$namespace = $wgRequest->getInt( 'namespace' );
$namespaces = $wgContLang->getNamespaces();
$wgOut->setPagetitle(
( $namespace > 0 amp;amp; in_array( $namespace, array_keys( $namespaces) ) ) ?
wfMsg( 'allinnamespace', str_replace( '_', ' ', $namespaces[$namespace] ) ) :
wfMsg( 'allarticles' )
);
if( isset($par) ) {
$this->showChunk( $namespace, $par, $to );
} elseif( isset($from) amp;amp; !isset($to) ) {
$this->showChunk( $namespace, $from, $to );
} else {
$this->showToplevel( $namespace, $from, $to );
}
}
/**
* HTML for the top form
*
* @param $namespace Integer: a namespace constant (default NS_MAIN).
* @param $from String: dbKey we are starting listing at.
* @param $to String: dbKey we are ending listing at.
*/
function namespaceForm( $namespace = NS_MAIN, $from = '', $to = '' ) {
global $wgScript;
$t = $this->getTitle();
$out = Xml::openElement( 'div', array( 'class' => 'namespaceoptions' ) );
$out .= Xml::openElement( 'form', array( 'method' => 'get', 'action' => $wgScript ) );
$out .= Html::hidden( 'title', $t->getPrefixedText() );
$out .= Xml::openElement( 'fieldset' );
$out .= Xml::element( 'legend', null, wfMsg( 'allpages' ) );
$out .= Xml::openElement( 'table', array( 'id' => 'nsselect', 'class' => 'allpages' ) );
$out .= "<tr>
<td class='mw-label'>" .
Xml::label( wfMsg( 'allpagesfrom' ), 'nsfrom' ) .
" </td>
<td class='mw-input'>" .
Xml::input( 'from', 30, str_replace('_',' ',$from), array( 'id' => 'nsfrom' ) ) .
" </td>
</tr>
<tr>
<td class='mw-label'>" .
Xml::label( wfMsg( 'allpagesto' ), 'nsto' ) .
" </td>
<td class='mw-input'>" .
Xml::input( 'to', 30, str_replace('_',' ',$to), array( 'id' => 'nsto' ) ) .
" </td>
</tr>
<tr>
<td class='mw-label'>" .
Xml::label( wfMsg( 'namespace' ), 'namespace' ) .
" </td>
<td class='mw-input'>" .
Xml::namespaceSelector( $namespace, null ) . ' ' .
Xml::submitButton( wfMsg( 'allpagessubmit' ) ) .
" </td>
</tr>";
$out .= Xml::closeElement( 'table' );
$out .= Xml::closeElement( 'fieldset' );
$out .= Xml::closeElement( 'form' );
$out .= Xml::closeElement( 'div' );
return $out;
}
/**
* @param $namespace Integer (default NS_MAIN)
* @param $from String: list all pages from this name
* @param $to String: list all pages to this name
*/
function showToplevel( $namespace = NS_MAIN, $from = '', $to = '' ) {
global $wgOut;
# TODO: Either make this *much* faster or cache the title index points
# in the querycache table.
$dbr = wfGetDB( DB_SLAVE );
$out = "";
$where = array( 'page_namespace' => $namespace );
$from = Title::makeTitleSafe( $namespace, $from );
$to = Title::makeTitleSafe( $namespace, $to );
$from = ( $from amp;amp; $from->isLocal() ) ? $from->getDBkey() : null;
$to = ( $to amp;amp; $to->isLocal() ) ? $to->getDBkey() : null;
if( isset($from) )
$where[] = 'page_title >= '.$dbr->addQuotes( $from );
if( isset($to) )
$where[] = 'page_title <= '.$dbr->addQuotes( $to );
global $wgMemc;
$key = wfMemcKey( 'allpages', 'ns', $namespace, $from, $to );
$lines = $wgMemc->get( $key );
$count = $dbr->estimateRowCount( 'page', '*', $where, __METHOD__ );
$maxPerSubpage = intval($count/$this->maxLineCount);
$maxPerSubpage = max($maxPerSubpage,$this->maxPerPage);
if( !is_array( $lines ) ) {
$options = array( 'LIMIT' => 1 );
$options['ORDER BY'] = 'page_title ASC';
$firstTitle = $dbr->selectField( 'page', 'page_title', $where, __METHOD__, $options );
$lastTitle = $firstTitle;
# This array is going to hold the page_titles in order.
$lines = array( $firstTitle );
# If we are going to show n rows, we need n 1 queries to find the relevant titles.
$done = false;
while( !$done ) {
// Fetch the last title of this chunk and the first of the next
$chunk = ( $lastTitle === false )
? array()
: array( 'page_title >= ' . $dbr->addQuotes( $lastTitle ) );
$res = $dbr->select( 'page', /* FROM */
'page_title', /* WHAT */
array_merge($where,$chunk),
__METHOD__,
array ('LIMIT' => 2, 'OFFSET' => $maxPerSubpage - 1, 'ORDER BY' => 'page_title ASC')
);
$s = $dbr->fetchObject( $res );
if( $s ) {
array_push( $lines, $s->page_title );
} else {
// Final chunk, but ended prematurely. Go back and find the end.
$endTitle = $dbr->selectField( 'page', 'MAX(page_title)',
array_merge($where,$chunk),
__METHOD__ );
array_push( $lines, $endTitle );
$done = true;
}
$s = $res->fetchObject();
if( $s ) {
array_push( $lines, $s->page_title );
$lastTitle = $s->page_title;
} else {
// This was a final chunk and ended exactly at the limit.
// Rare but convenient!
$done = true;
}
$res->free();
}
$wgMemc->add( $key, $lines, 3600 );
}
// If there are only two or less sections, don't even display them.
// Instead, display the first section directly.
if( count( $lines ) <= 2 ) {
if( !empty($lines) ) {
$this->showChunk( $namespace, $from, $to );
} else {
$wgOut->addHTML( $this->namespaceForm( $namespace, $from, $to ) );
}
return;
}
# At this point, $lines should contain an even number of elements.
$out .= Xml::openElement( 'table', array( 'class' => 'allpageslist' ) );
while( count ( $lines ) > 0 ) {
$inpoint = array_shift( $lines );
$outpoint = array_shift( $lines );
$out .= $this->showline( $inpoint, $outpoint, $namespace );
}
$out .= Xml::closeElement( 'table' );
$nsForm = $this->namespaceForm( $namespace, $from, $to );
# Is there more?
if( $this->including() ) {
$out2 = '';
} else {
if( isset($from) || isset($to) ) {
global $wgUser;
$out2 = Xml::openElement( 'table', array( 'class' => 'mw-allpages-table-form' ) ).
'<tr>
<td>' .
$nsForm .
'</td>
<td class="mw-allpages-nav">' .
$wgUser->getSkin()->link( $this->getTitle(), wfMsgHtml ( 'allpages' ),
array(), array(), 'known' ) .
"</td>
</tr>" .
Xml::closeElement( 'table' );
} else {
$out2 = $nsForm;
}
}
$wgOut->addHTML( $out2 . $out );
}
/**
* Show a line of "ABC to DEF" ranges of articles
*
* @param $inpoint String: lower limit of pagenames
* @param $outpoint String: upper limit of pagenames
* @param $namespace Integer (Default NS_MAIN)
*/
function showline( $inpoint, $outpoint, $namespace = NS_MAIN ) {
global $wgContLang;
$inpointf = htmlspecialchars( str_replace( '_', ' ', $inpoint ) );
$outpointf = htmlspecialchars( str_replace( '_', ' ', $outpoint ) );
// Don't let the length runaway
$inpointf = $wgContLang->truncate( $inpointf, $this->maxPageLength );
$outpointf = $wgContLang->truncate( $outpointf, $this->maxPageLength );
$queryparams = $namespace ? "namespace=$namespaceamp;" : '';
$special = $this->getTitle();
$link = $special->escapeLocalUrl( $queryparams . 'from=' . urlencode($inpoint) . 'amp;to=' . urlencode($outpoint) );
$out = wfMsgHtml( 'alphaindexline',
"<a href="$link">$inpointf</a></td><td>",
"</td><td><a href="$link">$outpointf</a>"
);
return '<tr><td class="mw-allpages-alphaindexline">' . $out . '</td></tr>';
}
/**
* @param $namespace Integer (Default NS_MAIN)
* @param $from String: list all pages from this name (default FALSE)
* @param $to String: list all pages to this name (default FALSE)
*/
function showChunk( $namespace = NS_MAIN, $from = false, $to = false ) {
global $wgOut, $wgUser, $wgContLang, $wgLang;
$sk = $wgUser->getSkin();
$fromList = $this->getNamespaceKeyAndText($namespace, $from);
$toList = $this->getNamespaceKeyAndText( $namespace, $to );
$namespaces = $wgContLang->getNamespaces();
$n = 0;
if ( !$fromList || !$toList ) {
$out = wfMsgWikiHtml( 'allpagesbadtitle' );
} elseif ( !in_array( $namespace, array_keys( $namespaces ) ) ) {
// Show errormessage and reset to NS_MAIN
$out = wfMsgExt( 'allpages-bad-ns', array( 'parseinline' ), $namespace );
$namespace = NS_MAIN;
} else {
list( $namespace, $fromKey, $from ) = $fromList;
list( , $toKey, $to ) = $toList;
$dbr = wfGetDB( DB_SLAVE );
$conds = array(
'page_namespace' => $namespace,
'page_title >= ' . $dbr->addQuotes( $fromKey )
);
if( $toKey !== "" ) {
$conds[] = 'page_title <= ' . $dbr->addQuotes( $toKey );
}
$res = $dbr->select( 'page',
array( 'page_namespace', 'page_title', 'page_is_redirect' ),
$conds,
__METHOD__,
array(
'ORDER BY' => 'page_title',
'LIMIT' => $this->maxPerPage 1,
'USE INDEX' => 'name_title',
)
);
if( $res->numRows() > 0 ) {
$out = Xml::openElement( 'table', array( 'class' => 'mw-allpages-table-chunk' ) );
while( ( $n < $this->maxPerPage ) amp;amp; ( $s = $res->fetchObject() ) ) {
$t = Title::makeTitle( $s->page_namespace, $s->page_title );
if( $t ) {
$link = ( $s->page_is_redirect ? '<div class="allpagesredirect">' : '' ) .
$sk->linkKnown( $t, htmlspecialchars( $t->getText() ) ) .
($s->page_is_redirect ? '</div>' : '' );
} else {
$link = '[[' . htmlspecialchars( $s->page_title ) . ']]';
}
if( $n % 3 == 0 ) {
$out .= '<tr>';
}
$out .= "<td style="width:33%">$link</td>";
$n ;
if( $n % 3 == 0 ) {
$out .= "</tr>n";
}
}
if( ($n % 3) != 0 ) {
$out .= "</tr>n";
}
$out .= Xml::closeElement( 'table' );
} else {
$out = '';
}
}
if ( $this->including() ) {
$out2 = '';
} else {
if( $from == '' ) {
// First chunk; no previous link.
$prevTitle = null;
} else {
# Get the last title from previous chunk
$dbr = wfGetDB( DB_SLAVE );
$res_prev = $dbr->select(
'page',
'page_title',
array( 'page_namespace' => $namespace, 'page_title < '.$dbr->addQuotes($from) ),
__METHOD__,
array( 'ORDER BY' => 'page_title DESC',
'LIMIT' => $this->maxPerPage, 'OFFSET' => ($this->maxPerPage - 1 )
)
);
# Get first title of previous complete chunk
if( $dbr->numrows( $res_prev ) >= $this->maxPerPage ) {
$pt = $dbr->fetchObject( $res_prev );
$prevTitle = Title::makeTitle( $namespace, $pt->page_title );
} else {
# The previous chunk is not complete, need to link to the very first title
# available in the database
$options = array( 'LIMIT' => 1 );
if ( ! $dbr->implicitOrderby() ) {
$options['ORDER BY'] = 'page_title';
}
$reallyFirstPage_title = $dbr->selectField( 'page', 'page_title',
array( 'page_namespace' => $namespace ), __METHOD__, $options );
# Show the previous link if it s not the current requested chunk
if( $from != $reallyFirstPage_title ) {
$prevTitle = Title::makeTitle( $namespace, $reallyFirstPage_title );
} else {
$prevTitle = null;
}
}
}
$self = $this->getTitle();
$nsForm = $this->namespaceForm( $namespace, $from, $to );
$out2 = Xml::openElement( 'table', array( 'class' => 'mw-allpages-table-form' ) ).
'<tr>
<td>' .
$nsForm .
'</td>
<td class="mw-allpages-nav">' .
$sk->link( $self, wfMsgHtml ( 'allpages' ), array(), array(), 'known' );
# Do we put a previous link ?
if( isset( $prevTitle ) amp;amp; $pt = $prevTitle->getText() ) {
$query = array( 'from' => $prevTitle->getText() );
if( $namespace )
$query['namespace'] = $namespace;
$prevLink = $sk->linkKnown(
$self,
htmlspecialchars( wfMsg( 'prevpage', $pt ) ),
array(),
$query
);
$out2 = $wgLang->pipeList( array( $out2, $prevLink ) );
}
if( $n == $this->maxPerPage amp;amp; $s = $res->fetchObject() ) {
# $s is the first link of the next chunk
$t = Title::MakeTitle($namespace, $s->page_title);
$query = array( 'from' => $t->getText() );
if( $namespace )
$query['namespace'] = $namespace;
$nextLink = $sk->linkKnown(
$self,
htmlspecialchars( wfMsg( 'nextpage', $t->getText() ) ),
array(),
$query
);
$out2 = $wgLang->pipeList( array( $out2, $nextLink ) );
}
$out2 .= "</td></tr></table>";
}
$wgOut->addHTML( $out2 . $out );
if( isset($prevLink) or isset($nextLink) ) {
$wgOut->addHTML( '<hr /><p class="mw-allpages-nav">' );
if( isset( $prevLink ) ) {
$wgOut->addHTML( $prevLink );
}
if( isset( $prevLink ) amp;amp; isset( $nextLink ) ) {
$wgOut->addHTML( wfMsgExt( 'pipe-separator' , 'escapenoentities' ) );
}
if( isset( $nextLink ) ) {
$wgOut->addHTML( $nextLink );
}
$wgOut->addHTML( '</p>' );
}
}
/**
* @param $ns Integer: the namespace of the article
* @param $text String: the name of the article
* @return array( int namespace, string dbkey, string pagename ) or NULL on error
* @static (sort of)
* @access private
*/
function getNamespaceKeyAndText($ns, $text) {
if ( $text == '' )
return array( $ns, '', '' ); # shortcut for common case
$t = Title::makeTitleSafe($ns, $text);
if ( $t amp;amp; $t->isLocal() ) {
return array( $t->getNamespace(), $t->getDBkey(), $t->getText() );
} else if ( $t ) {
return null;
}
# try again, in case the problem was an empty pagename
$text = preg_replace('/(#|$)/', 'X$1', $text);
$t = Title::makeTitleSafe($ns, $text);
if ( $t amp;amp; $t->isLocal() ) {
return array( $t->getNamespace(), '', '' );
} else {
return null;
}
}
}
Комментарии:
1. Вы просите способ разбиения списка на блоки по 100 или вы хотите, чтобы структура данных поддерживала список в этой форме?
2. Я прошу способ разбить этот список на блоки. Но эти 100 блоков должны быть выбраны особым образом. Результатом должен быть список, подобный списку Википедии.
3. на каком языке, на какой платформе?
4. PHP был бы лучшим. Я опустил эту информацию, потому что думал, что этот вопрос можно решить независимо от языка.
Ответ №1:
Не лучший подход, поскольку у вас нет возможности остановиться, когда вы дойдете до конца списка. Вы хотите разделить элементы, только если их больше, чем максимально (хотя вы можете добавить некоторую гибкость, так как вы можете дойти до стадии, когда у вас есть два элемента на странице).
Я предполагаю, что наборы данных на самом деле будут поступать из базы данных, но для удобства отображения используется ваш массив $items
В самом простом предположении, что он поступает с веб-страницы, которая отправляет индексный номер начала и конца, и что вы проверили, что эти номера действительны и очищены
$itemsPerPage = 50; // constant
$itemStep = ($end - $start) / $itemsPerPage;
if($itemStep < 1)
{
for($i = $start; $i < $end; $i )
{
// display these as individual items
display_link($items[$i]);
}
}
else
{
for($i = $start; $i < $end; $i = $itemStep)
{
$to = $i ($itemStep - 1); // find the end part
if($to > $end)
$to = $end;
display_to_from($items[$i], $items[$to]);
}
}
где функции отображения отображают ссылки так, как вы хотите. Однако одна из проблем, связанных с этим, заключается в том, что вы можете захотеть настроить элементы на странице, поскольку вы рискуете получить набор (скажем) 51 и получить ссылку от 1 до 49 и еще от 50 до 51.
Я не понимаю, почему вы размещаете его в группах в своем псевдокоде, поскольку вы переходите со страницы на страницу, выполняя дополнительные операции, поэтому вам нужно только начало и конец каждого раздела, пока вы не дойдете до страницы, на которой будут помещаться все ссылки.
— редактировать
Оригинал был неправильным. Теперь вы делите количество элементов, которые вам нужно просмотреть, на максимальное количество элементов, которые вы хотите отобразить. Если это 1000, это будет список из 20 элементов, если это 100 000, это будет каждые 2000. Если это меньше, чем показываемая вами сумма, вы можете показать их все по отдельности.
— отредактируйте еще раз — чтобы добавить еще немного о базе данных
Нет, вы правы, вы не хотите загружать 2 000 000 записей данных, и вам это не нужно. У вас есть два варианта: вы можете сделать подготовленное утверждение, например «выбрать * из статей, где article = ?» и перебирать результаты, получая по одному за раз, или, если вы хотите, сделать это в одном блоке — при условии использования базы данных mysql и кода выше,
$numberArray = "";
for($i = $start; $i < $end; $i = $itemStep)
{
$to = $i ($itemStep - 1); // find the end part
if($to > $end)
$to = $end;
// display_to_from($items[$i], $items[$to]);
if( $i != $start)
$numberArray = ", ";
$numberArray.= $i.", ".$to;
}
$sqlQuery = "Select * from articles where article_id in (".$numberArray.")";
... do the mysql select and go through the results, using alternate rows as the start and end
Это дает вам запрос типа «Выбрать * из статей, где article_id в (1,49,50,99,100,149 … и т.д.)»
Процесс, который, как обычный набор
Комментарии:
1. Большое вам спасибо! Причина, по которой я разделяю элементы на группы, заключается в том, что эта функция должна быть рекурсивной, не так ли? Когда у вас есть этот список для основного индекса, процедура должна повторяться для каждого из этих вложенных списков, верно? И ваше предположение было правильным: данные будут из базы данных, но я использовал здесь массив, поскольку его легче описать. Проблема с вашим решением заключается в том, что оно выполняет разделение только для основного индекса, а не для всех вложенных списков. И функция должна выполняться в приемлемое время даже для> 100 000 элементов.
2. Он не является рекурсивным, нет, поскольку пользователь, просматривающий сайт, выполняет рекурсию. Принцип работы с большим списком заключается в том, чтобы делать как можно меньше в любой момент (как и в жизни в целом!). Смысл разделения списка заключается в том, чтобы пользователь мог перемещаться по нему, поэтому каждый раз вам нужно только обработать $itemsPerPage , так как тогда они сами выбирают, на какую страницу они переходят. Это означало, что вы обрабатываете только 50 элементов на странице. Большинство страниц никогда не будут посещены. Нет смысла хранить их, поскольку к моменту появления следующего посетителя данные могут измениться.
3. Оригинал был неправильным. Что вы делаете сейчас с вашими 100 000 элементов, так это то, что начало равно 0, конец равен 100 000, поэтому шаг равен 100000/50 или 2000, так что вы проходите через все 2000, показывая элементы. Ваш пользователь нажимает на 3-ю ссылку, поэтому вы возвращаетесь на эту страницу, начиная с 6000 и заканчивая 7999, так что вы проходите цикл с шагом 40, вплоть до последней страницы
4. Спасибо, это звучит логично 🙂 Но не кажется ли вам, что Википедия предварительно генерирует и кэширует все списки? Действительно ли мне нужно получать все 100 000 элементов из базы данных каждый раз, когда пользователь просматривает этот индекс? Я не могу себе представить, что сервер сможет выбирать все элементы из базы данных и каждый раз проходить цикл !?
5. Википедия постоянно обновляет свой сайт, поэтому кэширование действительно не поможет, если кто-то добавил страницу, весь список придется создавать заново, а базы данных действительно очень быстры в таких вещах, лучше всего хранить данные там, а не в вашем приложении. Существуют и другие варианты получения больших наборов данных, такие как сбалансированные деревья (т. Е. Сохранение иерархии данных), но в данном случае они не помогут, поскольку вам не нужно получать все 100 000 элементов для базы данных, вы можете просто получать 100, которые вам нужны каждый раз. С помощью подготовленного оператора вам нужно только отправить ему идентификатор тех, которые вы хотите.
Ответ №2:
Мой подход в псевдокоде:
$items = array('air', 'automatic', 'ball', ..., 'yield', 'zero', 'zoo');
$itemCount = count($items);
$itemsPerPage = 50; // constant
$counter = 0;
foreach ($items as $item) {
$groupNumber = floor($counter/$itemsPerPage);
// assign $item to group $groupNumber
$counter ;
}
// repeat this procedure recursively for each of the new groups
Как вы думаете, это хороший подход? Можете ли вы улучшить или дополнить его?