14
\$\begingroup\$

On Wikipedia, if you click the first non-italicised internal link in the main text of an article that's not within parentheses, and then repeat the process, you usually end up on the "Philosophy" article (see this Wikipedia essay).

To test this idea, I made a simple Python module that does the "clicking" programmatically. Here's the code:

"""
The Philosophy Game
~~~~~~~~~~~~~~~~~~~~~~~~~

Clicking on the first non-parenthesized, non-italicized link,
in the main text of a Wikipedia article, and then repeating
the process for subsequent articles, usually eventually gets
one to the Philosophy article. (See
https://en.wikipedia.org/wiki/Wikipedia:Getting_to_Philosophy
for more information)

The Philosophy Game, written in Python, lets you do the clicking
programmatically.

Basic usage:

    >>> from philosophy import PhilosophyGame
    >>> game = PhilosophyGame('Python (programming language)')
    >>> for s in game.trace():
    ...     print(s)
    ...
    >>>

Handling errors:
    >>> from philosophy import *
    >>> game = PhilosophyGame('Python (programming language)')
    >>> try:
    ...     for s in game.trace():
    ...         print(s)
    ... except ConnectionError:
    ...     sys.exit('Network error, please check your connection')
    ... except MediaWikiError as e:
    ...     sys.exit('MediaWiki API error {1}: {2}'.format(e.errors['code'],
    ...                                                e.errors['info']))
    ... except LoopException:
    ...     sys.exit('Loop detected, exiting...')
    ... except InvalidPageNameError as e:
    ...     sys.exit(e)
    ... except LinkNotFoundError as e:
    ...     sys.exit(e)

Advanced options:

In this example, we set `end` to 'Multicellular organism', so that
instead of stopping at 'Philosophy', trace() stops there.
    >>> game = PhilosophyGame(page='Sandwich', end='Multicellular organism'):

In the following example, we set `dont_stop` to True, so that
trace() disregards the value of `end` and doesn't stop.
    >>> game = PhilosophyGame(page='Sliced bread', dont_stop=True)

Note that trace() will always raise exceptions in case a loop
is detected or if valid link cannot be found within the page.
"""

import requests
import urllib
from requests.exceptions import ConnectionError
import lxml.html as lh

class MediaWikiError(Exception):
    """
    Raised when the MediaWiki API returns an error.
    """
    def __init__(self, message, errors):
        super(MediaWikiError, self).__init__(message)
        self.errors = errors

class LoopException(Exception):
    """
    Raised when a loop is detected.
    """
    pass

class InvalidPageNameError(Exception):
    """
    Raised when an invalid page name is
    passed to self.trace().
    """
    pass

class LinkNotFoundError(Exception):
    """
    Raised when no valid link is found
    after parsing.
    """
    pass

class PhilosophyGame():
    """
    The main PhilosophyGame class.
    """
    BASE_URL = 'https://en.wikipedia.org/w/api.php'
    HEADERS = { 'User-Agent': 'The Philosophy Game/0.1' }
    def __init__(self, page=None, end='Philosophy', dont_stop=False):
        """
        Initialize object with initial page name to start with.

        Args:
            page: the initial page name to start with. (optional,
            defaults to a random page)

        Raises:
            InvalidPageNameError: if page is not a valid mainspace
            page name
        """
        if page is None:
            params = dict(action='query', list='random', rnlimit=1,
                        rnnamespace=0, format='json')
            result = requests.get(self.BASE_URL, params=params,
                                headers=self.HEADERS).json()
            if 'error' in result:
                raise MediaWikiError('MediaWiki error',
                    result['error'])
            self.page = result['query']['random'][0]['title']
        else:
            self.page = page

        if not PhilosophyGame.valid_page_name(self.page):
            raise InvalidPageNameError("Invalid page name '{0}'"
                                        .format(self.page))
        self.link_count = 0
        self.visited = []
        self.end = end
        self.dont_stop = dont_stop

    @staticmethod
    def strip_parentheses(string):
        """
        Remove parentheses from a string, leaving
        parentheses between <tags> in place

        Args:
            string: the string to remove parentheses from
        Returns:
            the processed string after removal of parentheses
        """
        p = a = 0
        result = ''
        for c in string:
            # When outside of parentheses within <tags>
            if p < 1:
                if c == '<':
                    a += 1
                if c == '>':
                    a -= 1

            # When outside of <tags>
            if a < 1:
                if c == '(':
                    p += 1
                if p > 0:
                    result += ' '
                else:
                    result += c
                if c == ')':
                    p -= 1

            # When inside of <tags>
            else:
                result +=c

        return result

    @staticmethod
    def valid_page_name(page):
        """
        Checks for valid mainspace Wikipedia page name
        """
        return (page.find('File:') == -1
            and page.find('File talk') == -1
            and page.find('Wikipedia:') == -1
            and page.find('Wikipedia talk:') == -1
            and page.find('Project:') == -1
            and page.find('Project talk:') == -1
            and page.find('Portal:') == -1
            and page.find('Portal talk:') == -1
            and page.find('Special:') == -1
            and page.find('Help:') == -1
            and page.find('Help talk:') == -1
            and page.find('Template:') == -1
            and page.find('Template talk:') == -1
            and page.find('Talk:') == -1
            and page.find('Category:') == -1
            and page.find('Category talk:') == -1)

    def trace(self, page=None, whole_page=False):
        """
        Visit the first non-italicized, not-within-parentheses
            link of page recursively until the page self.end
            (default: 'Philosophy') is reached.

        Args:
            page: The Wikipedia page name to start with
            (optional, defaults to self.page)
        Returns:
            A generator with the page names generated in sequence
            in real time (including self.end).
        Raises:
            MediaWikiError: if MediaWiki API responds with an error
            requests.exceptions.ConnectionError: if cannot initiate request
            LoopException: if a loop is detected
            InvalidPageNameError: if invalid page name is passed as argument
            LinkNotFoundError: if a valid link cannot be found for
            page
        """

        if page is None:
            page = self.page

        if not PhilosophyGame.valid_page_name(page):
            raise InvalidPageNameError("Invalid page name '{0}'"
                    .format(page))
        params = dict(action='parse', page=page, prop='text',
                    format='json', redirects=1)

        if not whole_page:
            params['section'] = 0

        result = requests.get(self.BASE_URL, params=params,
                    headers=self.HEADERS).json()

        if 'error' in result:
            raise MediaWikiError('MediaWiki error',
                result['error'])

        title = result['parse']['title'].encode('utf-8')

        # Don't yield if whole page requested
        # (which should only be done as a second attempt)
        if not whole_page:
            yield title

        # This needs to be done AFTER yield title
        # (The only) normal termination
        if not self.dont_stop and page == self.end:
            return
        raw_html = result['parse']['text']['*'].encode('utf-8')
        html = lh.fromstring(raw_html)

        # This takes care of most MediaWiki templates,
        # images, red links, hatnotes, italicized text
        # and anything that's strictly not text-only
        for elm in html.cssselect('.reference,span,div,.thumb,'
                                + 'table,a.new,i,#coordinates'):
            elm.drop_tree()

        html = lh.fromstring(PhilosophyGame.strip_parentheses(
                            lh.tostring(html)))
        link_found = False
        for elm, attr, link, pos in html.iterlinks():
            # Because .iterlinks() picks up 'src' and the like too
            if attr != 'href':
                continue
            next_page = link

            # Must be a valid internal wikilink
            if next_page[:len('/wiki/')] != '/wiki/':
                continue

            # Extract the Wikipedia page name
            next_page = next_page[len('/wiki/'):]

            # Decode escaped characters
            next_page = urllib.unquote(next_page)

            # Skip non-valid names
            if not PhilosophyGame.valid_page_name(next_page):
                continue

            # Links use an underscore ('_')
            # instead of a space (' '), this
            # fixes that
            next_page = next_page.replace('_', ' ')

            # Eliminate named anchor, if any
            pos = next_page.find('#')
            if pos != -1:
                next_page = next_page[:pos]

            # Detect loop
            if next_page in self.visited:
                raise LoopException('Loop detected')

            link_found = True
            self.link_count += 1
            self.visited.append(page)

            for m in self.trace(next_page):
                yield m

            break
        if not link_found:
            if whole_page:
                raise LinkNotFoundError(
                        'No valid link found in page "{0}"'.format(
                            page.encode('utf-8')))
            else:
                for m in self.trace(page, whole_page=True):
                    yield m

Basic usage of the module would be something like:

from philosophy import PhilosophyGame

game = PhilosophyGame()
for page in game.trace():
    print(page)

The problem is, it takes a long time to fetch the result of a MediaWiki API query, parse it as JSON, extract the parsed HTML text, remove text within parentheses and some tags (e.g. <i>), then get the first link, follow it and repeat the process.

To optimize the approach, I altered the trace() method so that instead of parsing the whole page, it only requests parsed text of the lead section of a page, and only request the whole page as a second attempt when no link could be found the first time, but it's still pretty slow.

I do realize that using a local Wikipedia dump would speed up the whole process, but I was wondering if there was a way to optimize the existing approach.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ In trace(), the expression next_page[:len('/wiki/')] != '/wiki/' is equivalent to not next_page.startswith('/wiki/'). \$\endgroup\$
    – BenC
    Dec 20, 2015 at 20:35
  • \$\begingroup\$ it takes a long time to fetch the result of a MediaWiki API query, parse it as JSON, extract the parsed HTML text, remove text within parentheses and some tags (e.g. <i>), then get the first link do you have some timing measurement to support this? Do you know which part is the slowest? Which part can you actually improve? \$\endgroup\$
    – oliverpool
    Dec 20, 2015 at 22:07
  • \$\begingroup\$ @oliverpool: I just did a timing test using line_profiler (which basically tells you about the time each line in your code took) and apparently in both __init__() and trace(), fetching the contents of the GET request is what took the most time (over 90% in both cases). I changed the headers to include Accept-Encoding: gzip (MediaWiki supports gzip) but the improvement wasn't much (39.5474 to 37.3156 seconds with "Koseč" as the starting point). \$\endgroup\$
    – Sumit
    Dec 21, 2015 at 9:28
  • \$\begingroup\$ @Sumit : so even if you drastically improve the Python code, you can't get much more than a 10% improvement without a dump \$\endgroup\$
    – oliverpool
    Dec 21, 2015 at 9:56

2 Answers 2

5
\$\begingroup\$

Reduce repetition

@staticmethod
def valid_page_name(page):
    """
    Checks for valid mainspace Wikipedia page name
    """
    return (page.find('File:') == -1
        and page.find('File talk') == -1
        and page.find('Wikipedia:') == -1
        and page.find('Wikipedia talk:') == -1
        and page.find('Project:') == -1
        and page.find('Project talk:') == -1
        and page.find('Portal:') == -1
        and page.find('Portal talk:') == -1
        and page.find('Special:') == -1
        and page.find('Help:') == -1
        and page.find('Help talk:') == -1
        and page.find('Template:') == -1
        and page.find('Template talk:') == -1
        and page.find('Talk:') == -1
        and page.find('Category:') == -1
        and page.find('Category talk:') == -1)

and page.find and == -1 are repeated \$16\$ times. Use a generator comprehension instead:

return all(page.find(non_main) == -1 for non_main in NON_MAIN_CATEGORIES)

Where NON_MAIN_CATEGORIES may be saved as a constant either top-level or inside this class.

in

Your usage of find looks like a weird substitute for in, you probably mean:

non_main not in page

When you use .find == -1

So at last we get:

return all(non_main not in page for non_main in NON_MAIN_CATEGORIES)

Some REPL example usage of in to clear this up:

>>> "example".find("e")
0
>>> "example".find("x")
1
>>> "example".find("z")
-1
>>> "example".find("z") == -1
True
>>> not "z" in "example"
True
>>> ("example".find("z") == -1) == (not "z" in "example")
True
>>> "z" not in "example" # Just some syntactic sugar
True

Philosophy and string stripping: Separation of concerns

Why is strip_parentheses(string) a method of the philosophy game class? Maybe you need this functionality inside the game, but it is a minor detail.

Think re-use, would anyone think that stripping parenthesis is put inside a class for Philosophy Wikipedia surfing?

Just put it free-floating or inside a string_utils module that you may import.

Actually, why a class?

Ignoring __init__, that any class must have, valid_page_name that is trivial, and strip_parentheses that should really not be there, thePhilosophyGame class just contains one function.

When you have only one function in a class, you can simplify and avoid the class completely.

def philosophy_game(start=None, end='Philosophy', ...):
    # Implementation

The usage also a little becomes easier:

print(list(philosophy_game('Dog')))

Double negatives

I find double negatives needlessly confusing.

if not self.dont_stop and page == self.end:
    return

Requires some thinking, while:

if self.should_end and page == self.end

Reads in a fraction of a second.

Or you may just use a noun instead of dont in the variable name:

if not self.infinite and page == self.end:
    return

Either is easier to understand than double negation.

\$\endgroup\$
1
\$\begingroup\$

I don't like small trailing else blocks, I usually prefer to flip the conditions so it's easier to see what happens in each case:

    if page is not None:
        self.page = page
    else:
        params = dict(action='query', list='random', rnlimit=1,
                      rnnamespace=0, format='json')
        result = requests.get(self.BASE_URL, params=params,
                              headers=self.HEADERS).json()
        if 'error' in result:
            raise MediaWikiError('MediaWiki error',
                result['error'])
        self.page = result['query']['random'][0]['title']

It's also strange to instantiate a dict with the function instead of literal syntax. Why not just do this:

        params = {'action': 'query', 'list': 'random', 'rnlimit': 1,
                  'rnnamespace': 0, 'format': 'json'}

strip_parentheses is very confusing with all the single character names. What are p c and a? You seem to be using a for level of nesting, so why not nesting_level? c is character since it's the iteration of the string and p is, nested_parentheses? Even if you can't get an entirely clear name, you can do better than p and at least add a comment.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.