text:
# A Scalable Architecture for Harvest-Based Digital Libraries - The ODU/Southampton Experiments

## 1 Introduction

11footnotetext: X.Liu, K.Maly, M.Zubair are with Computer Science Department,Old Dominion University, USA22footnotetext: T.Brody, S.Harnad, L.Carr are with Intelligence, Agents, Multimedia Group, Electronics and Computer Science, University of Southampton, UK33footnotetext: M.L.Nelson is with NASA Langley Research Center, USA

The Open Archives Initiative Protocol for Metadata Harvesting (OAI-PMH) is an important new infrastructure for supporting distributed networked information services. OAI promotes interoperability through the concept of metadata harvesting. The OAI framework supports Data Providers (DPs) and Service Providers (SPs). SPs develop value-added services based on the information collected from DPs. DPs are simply collections of harvestable metadata that may or may not contain additional services and content. This paper introduces the concepts of OAI-PMH proxies, OAI-PMH caches, OAI-PMH gateways as tools for the optimization of the functioning of the DP/SP model underlying the OAI-PMH.

The OAI-PMH uses HTTP-based request-response communication between a DP and an SP. The XML-formatted metadata is encoded in the HTTP response, which makes on-demand services possible. Using OAI-PMH, one DP may be harvested by any number of SPs, each possibly implementing different services. These service providers can interoperate using the multiple-resolution capability (one identifier is resolved to multiple instances) based on unique identifiers. In OAI-PMH, the metadata is distributed and replicated in many different places and potentially provides a highly redundant and fault-tolerant system.

The Old Dominion University (ODU) Digital Library Group and the University of Southampton have been engaged in research focused on various OAI-PMH services. The goal of this research is to achieve interoperability, scalability and reliability of OAI-PMH services.

Over the past two years, ODU has developed the Arc , Archon , Kepler , and DP9  services. Arc and Archon are federated searching services based on the OAI-PMH; they focus on the process of building a unified search interface over heterogeneous collections. Kepler is an end-user software that allows the individual to easily create and maintain a small, OAI-compliant archive. DP9 is a gateway service that allows general search engines (e.g. Google, Inktomi, etc.) to index OAI-PMH-compliant archives.

As part of the JISC/NSF Open Citation Project  (and previously the Open Journals Project), the University of Southampton Intelligence, Agents, Multimedia Group (IAM) has researched and developed methods for citation linking and analysis of the refereed scientific literature. Recent efforts have focused on CiteBase Search . CiteBase is an impact-ranking OAI-PMH SP, providing a federated searching service, citation linking (resolving author-provided references to their OAI-PMH-available targets), and citation analysis. CogPrints  is an archive, hosted at Southampton, that allows authors to archive their articles (e-prints) for free in a freely accessible web service . The software behind CogPrints, ePrints.org , has been developed by Southampton and released under Open Source. Now anyone, from individuals to institutions, may create their own self-archiving repositories. ePrints.org is fully OAI-PMH-compliant.

In these efforts we notice challenges faced by OAI-PMH based applications, namely:

During the testing of DPs, numerous problems were found. Not all archives strictly follow the OAI-PMH; many have XML syntax and encoding problems. The UPS Prototype  also found significant problems with metadata, however, with OAI-PMH, syntax for metadata is strictly defined (XML schema validation), problems still appear. This suggests that some DPs do not strictly check their OAI-PMH implementations.

The stability and service from DPs are difficult to predict since many factors may influence DP availability and efficiency . If a large DP is periodically unavailable, this can be a serious problem for harvesting. A recent research points out that a significant number of DPs could not be harvested in the testing period .

OAI-PMH harvesting is resource-expensive to DPs, partially because the HTTP responses are dynamically generated, and DPs may need to keep current harvest sessions (harvesting may take several days for a large data set). Besides steps taken by individual DPs to improve services, a general infrastructure is required.

In OAI-PMH, several DPs may be harvested by many SPs, each providing different services for the same records. Cross-service linking and data sharing can be achieved by using the unique OAI identifiers. Unique identifiers also allow the detection of record duplication.

In this paper we discuss a joint effort between ODU and Southampton that addresses these problems using a variety of techniques. We present an architecture to achieve interoperability, scalability, and reliability by optimizing dataflow in DPs/SPs. This architecture introduces an OAI-PMH Proxy concept that could improve DP quality by fixing implementation problems just in time. An OAI-PMH Cache service improves data availability and avoids bottlenecks through Hierarchical Harvesting. An OAI-PMH Gateway translates operations from other resource discovery systems into operations in OAI-PMH and vice versa. We also discuss how to build a series of services such as cross-archive linking based on the suggested architecture.

The remainder of this paper is organized as follows. In Section 2 we discuss related work. In Section 3 we present an overview of the optimized model. We discuss each of the subsystems in Sections 4-8. In Section 9 we discuss several working applications, and we summarize in Section 10.

## 2 Related work

### 2.1 Global Research Archive

The driving force behind the development of OAI-PMH was the need for a common method of federating heterogeneous e-print archives into cross-archive search engines and other end-user services, e.g., the UPS prototype .

A global research archive can start with e-print archives, perhaps subject-, institution-, or publisher- based. The software e-Prints.org has been developed to support author self-archiving . This and other e-print archives can be harvested to form federated services, potentially a Global Research Archive, e.g., Scirus , Arc , CiteBase , and My.OAI .

This structured model for federated archives contrasts with CiteSeer , which is a web crawler that retrieves research articles from personal and institutional web sites, and automatically builds the bibliographic and reference data from the articles. There is no interoperability model underlying CiteSeer.

### 2.2 Caching and Replication

HTTP proxy and cache distribute load, reduce network traffic and access latency, and protect the network from erroneous clients . There are two basic approaches for web cache implementation: the passive cache only loads a data object as a result of a client’s request to access that object, and an active cache employs some mechanism to prefetch data  in advance of a request by a client.

Mirror software is designed to duplicate a directory hierarchy between two machines. It avoids copying files unnecessarily by comparing the file timestamps and file sizes before transferring .

### 2.3 Hierarchical Harvesting

The earlier Harvest project explored the concept of the hierarchical arrangement of object caches and focused on the content extraction for general web documents . After OAI-PMH was released, both Arc and CiteBase explored the issues of hierarchical harvesting in OAI-PMH SPs. The Open Digital Library project  and the OAI “result set filtering” whitepaper  explored using the OAI-PMH sets concept for OAI-PMH metadata filtering.

### 2.4 Unique Identifiers

Identifiers are a powerful tool for communication within and between communities. For example, the Handle system  and DOI (Digital Object Identifier)  provide a mechanism for implementing naming systems for arbitrary digital objects. The multiple-resolution capability becomes important in OAI-PMH community, as metadata may be widely replicated and modified, and many different services will be implemented on the same metadata records. An “intelligent” resolution service should be able to deliver different outcomes to a resolution request dependent on user-specified requirements .

In OAI-PMH, unique identifier unambiguously identifies an item within a repository, the format of the unique identifier must correspond to that of the URI syntax, Individual communities may develop community-specific URI schemes for coordinated use across repositories.

However, the unique identifiers may conform to a recognized URI scheme with greater scope. Especially the oai-identifier schema describes a specific, recommended implementation of unique identifiers which repositories may adhere to; oai-identifiers should have global scope and guaranteed global uniqueness. The oai-identifier has been widely accepted in implementation of OAI-PMH 1.1 and is further refined in the version 2.0 of the protocol by introducing a globally unique OAI URN. Both the ODU and Southampton implementations use the oai-identifier schema and rely on its uniqueness.

### 2.5 Citation Linking

Citation linking is the general term for hypertext linking the reference lists (the bibliography) in research articles to the cited articles. In recent years, citation linking has been extensively developed    . With the wide acceptance of OAI-PMH, new challenges are raised about cross-archive (i.e. cross collection) linking and cross-service linking. With various DPs providing metadata of different qualities and formats, cross-archive linking is necessary to integrate them into one unique linking environment. Similarly, the distributed and highly redundant OAI-PMH architecture allows different services to be built which, with context sensitive and dynamic cross-service linking  , could potentially be integrated.

Such integrated services might provide citation analysis for forward links (to articles that have referenced the current article), impact factors, co-citation analysis, and novel navigation methods .

### 2.6 Distributed Search vs. Harvest

There are two ways to implement DL interoperability, through distributed search or harvest. The distributed searching approach is studied in NCSTRL, Stanford Infobus . Currently, the harvesting approach has better scalability and is a realistic approach for a large number of existing DLs. It is studied in Harvest  and is the basis of OAI-PMH.

## 3 System Overview

The need for an optimized model is motivated by the major challenges faced in a basic OAI-PMH model, which can be seen in Figure 1. The basic structure of OAI-PMH supports two roles: the SP and the DP. Multiple SPs may harvest multiple DPs at the same time. If one DP has implementation problems (e.g., XML encoding), all SPs have to address these problems. If one DP is unavailable, all SPs have to wait until the DP comes up again, even if some SPs have already cached the data from the DP.

Figure 2 illustrates the optimized model based on the hierarchical harvesting. An OAI-PMH proxy dynamically forwards requests DPs with value-added services. For example, it can dynamically fix common XML encoding errors and translate between different OAI-PMH versions. An OAI-PMH cache caches metadata and can filter and refine them before exposing them to SPs. It also serves as a simple cache that reduces the load on source DPs and improves DP availability. An OAI-PMH gateway can convert the OAI-PMH to other protocols and applications. For example, the gateway could provide value-added services like automatic citation extraction, or conversion between different protocols (SOAP, Z39.50) and OAI-PMH. An end-user service will present various services such as search and citation linking. Figure 2 illustrates how each layer may fetch data from any of its lower layers depending on availability and service type.

## 4 Data Provider

The OAI-PMH is designed as a low-barrier and structured method for DPs to expose hidden content to add-on services. (We define “hidden” as both data that cannot be accessed via the Web, and data that can only be accessed through proprietary web interfaces)

A DP, using OAI-PMH, exposes metadata for the resources for which it is responsible. Any (or many) metadata formats may be exposed for any given resource, although to be OAI-PMH compliant the DP must support Dublin Core.

A DP does not necessarily provide any added value from the end-user’s perspective; it simply gives OAI-PMH compliant harvesters access to the raw metadata in the repository. However, a richer metadata resource allows more interesting services to be built on top of it. For example, DPs that are collections of research literature (articles with bibliographies), may export the resource’s reference list as well as the current authors, title, and so on.

The first step to building value-added services on repositories is harvesting their metadata. Where there are OAI-PMH implementation faults, SPs must try to work around these problems, or, as we suggest, use a separate layer to fix errors with the DP’s implementation: an OAI-PMH Proxy.

## 5 OAI-PMH Proxy

From a harvester’s point of view, the most convenient solution to incorrectly implemented DPs is to place a layer (i.e. a proxy) over source repositories that can be trusted to provide correct responses to the harvester’s requests. The proxy can protect the network from erroneous and malicious clients, for example, a proxy can serve as the single access point for outside world to DPs inside a firewall.

An OAI-PMH proxy can either act as an HTTP proxy or be OAI-PMH-specific. As an HTTP proxy, it effectively becomes a transparent layer accepting HTTP requests and responding with HTTP responses. As an OAI-PMH-specific proxy, it must re-write request URLs; for an example of mapping a given subdirectory to a source baseURL, see Figure 3.

An OAI-PMH proxy will fix the following errors:

OAI-PMH uses the Unicode’s UTF-8 character encoding to support international character sets by using multiple bytes for non-English characters. As an OAI-PMH response is received from a repository, the proxy can replace any faulty character encoding that would normally cause an XML parser to fail.

The mark-up characters used in XML must be encoded when used in string data. Similar to recent web browsers, the proxy can use heuristics to determine whether a mark-up character is actually part of mark-up, or should be encoded.

XML requires that all arguments to XML elements are quoted, and heuristics can be used to fix some quoting errors. An advanced proxy may be able to fix missing, or out-of-order, XML elements; however, this can easily lead to untraceable errors.

A proxy can check the validity of the response it receives. It can check that the schemas used in the response are the ones used by the OAI-PMH, and that the XML can be validated against those schemas.

Whereas character and XML encoding problems can be fixed in a stream, more complex errors require caching the entire OAI-PMH response. This requirement leads naturally to an OAI-PMH Cache that is capable of storing and fixing OAI-PMH responses.

## 6 OAI-PMH Aggregation and Caching

OAI-PMH caching/aggregation (an OAIA) expands the DP/SP model with a middle layer that aggregates/caches responses from source DPs. This feature provides benefits to both aggregated DPs, and SPs that choose to harvest from the OAIA.

### 6.1 Caching Data Providers

A DP can be harvested by any number of services. Frequent harvesting by many services can result in a significant overhead for providers, who can range from small collections running on simple web-scripts to large multi-million record collections running on powerful databases. A small provider may have inefficient systems or few resources, and a large provider may not appreciate an unreliable harvester continually requesting very large data sets.

An OAIA solves this problem by mirroring DP’s metadata, so a few large aggregators (efficiently implemented) can serve many other OAI-PMH services, including downstream aggregators.

### 6.2 Aggregation

When deciding which repositories to harvest from, an SP must consider whether the repository content is relevant, whether the repository is reliable, and how often the SP should check that repository for updates.

A hierarchical OAIA structure can reduce this problem by avoiding duplication of the efforts of many SPs. For example, an SP may want to provide an index of all the music manuscript repositories of a given country. That SP can then expose the aggregated collection to an international SP, saving the international SP the effort of harvesting from every repository in every country.

### 6.3 Advantages Over HTTP Caching

An OAIA is similar to an HTTP cache; specifically, they both distribute load away from the server (the DP) and closer to the client (the SP).

An OAIA is, however, an active cache - it requests new records from the known repositories in advance. This means a repository’s records will always be available from the cache to downstream harvesters, even if the repository itself is unavailable.

An important role for an aggregator is providing quick access to many, smaller collections. By prefetching records from its source repositories, an OAIA can provide a downstream harvester with all the aggregated records in one session.

### 6.4 Datestamping

Incremental harvesting in OAI-PMH uses datestamping; that is, a harvester only needs to request records that are new or have changed since the last time it checked the repository.

With hierarchical harvesting the OAIA must update the datestamp when it harvests a record - because the record is “new” to the OAIA. When a downstream harvester harvests from the OAIA, it will receive all the new records in the OAIA, even if the original datestamp of the record was before the date of harvest.

### 6.5 Identifiers

An OAIA can either maintain or change the oai-identifiers for records that it harvests (and reexports).

By maintaining the record’s oai-identifier, the OAIA can become a nearly transparent layer in a hierarchical system (nearly transparent, because it introduces a delay between a record being created by DPs, and it being harvested from the OAIA). Maintaining oai-identifiers allows a harvester to change sources without causing inconsistent records.

OAI-PMH 2.0 introduces a provenance schema for use in the optional “about” field of records (“about fields” are for things that describe the metadata record). This schema allows the history of the record to be recorded: it stores the details of each OAI-PMH service that the record passes through as it goes down the hierarchy, from repository to eventual end-user service.

Provenance can be used to check the originality of the record, identify the change history of the record when it travels around the system, and to extract the original datestamp.

### 6.6 Identifier Collisions

When there is more than one path from a DP to an SP, the SP may need to resolve a collision between two or more records with the same oai-identifier.

Figure 4 shows how one record (with a unique oaiidentifier), may appear twice to a harvester. Three repositories, a, b, and x, are being harvested by two aggregators, a+x and b+x. When the service provider a+b+x harvests from a+x and b+x, it will get duplicates for every record from the data provider x.

To resolve collisions, a service provider can either store both records or attempt to discard one. The following are some possible policies for record discarding:

If colliding records are the same, or close, the duplicates could be safely discarded.

The SP in Figure 4 may, for example, trust OAIA b+x more than OAIA a+x, in which case the SP could discard or overwrite any colliding records harvested from OAIA a+x.

It may be possible to distinguish the most recent (and hence most authoritative) record using the datestamps given by the aggregator’s provenance data (e.g., OAIAs a+x and b+x in Figure 4).

## 7 OAI-PMH-Gateway, Value-Added Services

A gateway between two resource discovery systems translates operations from one system into operations in another system. An OAI-PMH Gateway is responsible for converting OAI-PMH for use by other applications and vice-versa. Unlike the OAI-PMH Cache and Proxy, the Gateway service does not necessarily retain the original data or OAI-PMH interface. The objective of a Gateway is to extend OAI-PMH-compliant repositories to other protocols or applications; for example:

A protocol broker could convert HTTP-based OAI-PMH requests to SOAP messages, or extend OAI-PMH to a Web Service model.

A gateway for web crawlers could translate OAI-PMH-compliant repositories to a series of linked web pages, which allows web search engines that do not support the OAI-PMH to index the “Deep Web” contained within OAI-PMH-compliant repositories.

A gateway could cache the full-text document, and then provide value-added services, such as citation extraction, which can then be re-exposed through its own OAI-PMH interface.

A subject gateway could help build a topic-specific service by harvesting records and then exposing them by subject criteria.

A gateway service may create a large overhead for DPs, especially if the gateway is designed to serve machine-based applications (e.g., web crawlers). This situation is where the OAI-PMH Cache is relevant because the hierarchical structure of OAI-PMH Cache will reduce the overhead for the source DPs to a minimum. At the same time, the gateway service itself could use flow control mechanisms, such as HTTP-throttle software, to reduce the overhead.

## 8 End-user Service, Search/Citation, Cross Archive Linking Service

There are several considerations for implementing end-user services using the OAI-PMH:

The globally unique oai-identifier could be a basis for SP/DP interoperability.

With various DPs providing metadata of different qualities and formats, cross-archive linking is necessary to integrate them into one linking environment.

Many services may be implemented on the same harvested records. A combination of these services will be very useful.

While OAI-PMH defines Dublin Core as the mandatory metadata format, each provider/community may implement its own metadata sets; supporting this variety of metadata sets is a challenging issue.

DP supports for web presentation of proprietary XML metadata formats.

Different SPs can be aware of and link to each other by using OAI-PMH unique identifiers. A distributed service model could be accomplished by sharing different services.

Figure 5 shows how to support parallel metadata presentation by XSLT processing. DPs will export their metadata (by OAI-PMH) and presentation format (by XSLT). An SP harvests the metadata and builds a search interface. The resource discovery is performed by the SP, and the final presentation of the data is accomplished by the DP’s XSLT. With this mechanism, DPs may define an explicit method for presenting the metadata format, which is especially useful for rarely used or repository-specific metadata formats. OAI-PMH 2.0 introduces a ”branding” mechanism for the SP to render the metadata in the stylesheet specified by the DP.

For research literature OAI-PMH can provide a transport mechanism for the bibliographies, as well as metadata. The references can then be harvested by ”reference-aware” services that can provide linking services (e.g., by generating a URL to the full-text from the bibliographic reference). Further services can be built on the linked references, such as citation analysis. By aggregating many archives of research literature, one linking service will be able to provide reference links across many small archives.

Currently, there is no widely used XML metadata format in DPs that supports bibliographic references. Many archives, if they support references at all, will only export the text of the reference, and rely on add-on services to parse the text into bibliographic components. Other archives (e.g., Biomed Central), whose core document format is XML, will be able to provide fully marked-up references, so that only minimal processing will be required by linking services. The standardization of OpenURL, which is gathering growing support as an open and extensible system for reference linking using HTTP URLs, may result in a widely-used bibliographic-aware metadata format .

A citation-linking system is likely to be hierarchical because middle normalization layers will be needed to parse source archive reference lists into a common format that end-user services can link to bibliographic databases; furthermore references will also need to be provided in a format understood by the end-user.

## 9 Experiments

### 9.1 OAI-PMH-Proxy

Our first experiment is an OAI-PMH-specific proxy that takes a URL of the format:
http://foo.org/OAIProxy/{repositoryid}?{oai verb}
Its function is to filter XML encoding errors. This proxy relies on a preexisting mapping table between an OAI-PMH repository ID and a baseURL. When an OAI-PMH request is issued, the proxy forwards the request to the corresponding data provider. The XML response is parsed by a DOM parser; if any XML encoding errors exist, the proxy tries to delete bad records based on the detailed error message from the DOM parser. The proxy then returns the corrected XML response.

### 9.2 OAI Aggregation/Caching/Filtering

An OAI-PMH cache service has been explored in several experiments, including OAI Aggregator, Arc, and CiteBase. Both Arc and Citebase act as DPs disseminating Dublin Core metadata harvested from other DPs.

OAIA is specially designed to mirror OAI repositories. OAIA creates a duplicate of all available data from the source repositories, excluding the set hierarchy (with OAI 1.1, the set hierarchy can only be ascertained through exhaustive querying of each set).

OAIA is designed to facilitate OAI-PMH Gateway services, which rely on fast, reliable access to OAI repositories. For DP9, this consists of a few list identifiers requests, followed by large numbers of individual record requests (as a Web crawler requests the corresponding record’s web page). Otherwise, this kind of behavior can lead to large numbers of (possibly unwanted) requests to source repositories exposed through DP9.

OAIA also acts as a gateway from legacy OAI-PMH implementations (1.x) to the most recent version of the OAI-PMH (2.0). As well as being able to harvest from any repository that has been OAI-PMH-compliant, OAIA converts the required Dublin Core metadata format to the most recent OAI-PMH version.

Given a new repository URL, OAIA issues an Identify request. The Identify response is stored so an SP can retrieve from OAIA the source repository’s data policies, etc. A ListMetadataFormats request is issued to find out which metadata formats are supported. Each record is then requested for each metadata format (either using the batch command ListRecords, or GetRecord, depending on the repository’s reliability). The metadata is stored as it was received from the source repository, ready for an SP to harvest. The record’s datestamp is changed to the time the record was harvested by OAIA.

OAIA provides two views to harvesters of the records it has collected: the aggregated collection, or individual repositories by using a wrapped URL.

When an aggregated OAIA collection receives a ListMetadataFormats request, it lists all the metadata formats used by any of the harvested repositories (which may include variants of the same metadata format). When the same request is made to a wrapped repository, it lists only the metadata formats supported by that repository.

### 9.3 Gateway

DP9 is a gateway service that allows general search engines, (e.g. Google, Inktomi) to index OAI-compliant archives. DP9 does this by providing persistent URLs for records, and converting them to OAI-PMH queries against the appropriate repository when the URL is requested. This service allows search engines that do not support the OAI-PMH to index the ”Deep Web” contained within OAI-PMH-compliant repositories.

DP9 is a gateway service; it does not cache the records and only forwards requests to corresponding DPs. This process ensures DP9 records are always up to date; however, its quality of service is highly dependent on the availability of DPs. On the other hand, an aggressive crawler using DP9 can rapidly send requests without regard for the load it places on the DPs. The robot exclusion protocol  at the DP site will not be observed because the requests originate from DP9. The OAIA is used relieve the load on DPs.

Another gateway service is the reference extraction module in CiteBase. CiteBase extracts the bibliography from arXiv.org documents and exposes them by an additional OAI-PMH interface. These data are then harvested by ODU to build its own citation service.

CiteBase adds reference data by harvesting new records from a repository’s OAI-PMH interface, then separately downloading the full text for parsing. The parsed bibliography is added to the existing metadata, and is used by CiteBase or harvested by other services.

The CiteBase concept could be extended from the current supported repository (arXiv.org ) to a general service for any full-text scientific repository - assuming tools can be developed to parse the bibliography.

### 9.4 End-User Services

Both Archon and CiteBase implement a cross-archive search interface; Archon focuses more on harvesting heterogeneous collections and builds an interactive search interface based on harvested metadata, and CiteBase concentrates on automatic reference extraction. Both applications may harvest from the same repository (e.g. arXiv.org ) and implement different services for the same record. With the quick adoption of OAI-PMH, we believe this will become a common situation. We implemented two prototypes for cross-linking between Archon and CiteBase (Figure 6).

The first approach is to reexpose value-added metadata through an OAI-PMH interface. By this method Archon harvests citation data from CiteBase, APS, CERN and other sources, it then builds a cross archive linking service such as a citation in APS may lead to document in CiteBase and vice-versa. Another prototype is based on dynamic linking: both services link to a broker page, and the broker page dynamically checks whether a service exists for a specific record. If so, it adds a link to the corresponding SP. In order to know which records are available in advance, the broker issues an OAI GetRecord lookup to the target service (which has an OAI-PMH export). Based on the reply, the broker knows whether a record is harvested. We envision that a DP may also link to this broker page for additional services for its data.

## 10 Summary

The OAI-PMH is an important infrastructure for supporting distributed networked information services. This paper introduces the concepts of OAI-PMH proxies, OAI-PMH caches, OAI-PMH gateways as tools for the optimization of the functioning of the DP/SP model underlying the OAI-PMH. To demonstrate the usability of this framework, we have built several prototype services. These demonstration systems and source codes are available at the web sites of both ODU and the Southampton group.

## 11 Acknowledgements

Our thanks to Herbert Van de Sompel and Steve Hitchcock for providing valuable input and reviewing the manuscript.


format: text

text:
# Chaotic Synchronization Via Minimum Information Transmission

## I Introduction

The possibility to synchronize the dynamics of two identical chaotic systems Fujisaka and Yamada (1983); Pikovsky (1984); Afraimovich et al. (1986); Pecora and Caroll (1990) is determined by two factors (to be precise the case of unidirectional impact of one system on the other is assumed, i.e., the situation ”drive system - response system” is considered). First, the way the drive system affects the response system. Significant progress has been achieved here that enables synchronization not only of chaotic systems but also of systems with hyperchaos Peng et al. (1996); Macau et al. (2002). Second, it is determined by the sensitivity of the chaotic synchronization to distortions of the signal in the coupling channel, in particular, to the effects of filtering and to the presence of noise Brown et al. (1994). The attempts to damp this sensitivity are being made both in the direction of development of more robust schemes Minai and Anand (1999); T.L.Carroll (2001) and in the direction of correction (reconstruction) of a signal, distorted in the coupling channel, into its original form at the input of the responce system. For instance, in the case of a noisy signal, the reconstruction is considered to be the cleaning of this signal from noise Abarbanel (1996); Kantz and Schreiber (1997); Kostelich and Yorke (1988); Kostelich and Schreiber (1993); Sternickel et al. (2001); Rosa et al. (1997). Hence, the problem is to reconstruct with a high precision the output signal of the drive system at the input of the response system. However, for this purpose, transmission of the signal itself through the coupling channel is not necessary. Instead, one can transmit the minimal information about the signal necessary to reconstruct (recover) the initial signal at the input of the response system, i.e. to replace the coupling channel by the communication channel. From the viewpoint of the information theory the second approach to reconstruction of the signal at the input of the response system can be preferable as it (i) requires less information to be transmitted and (ii) this information can be presented (coded) so that it is more robust to the disturbances in the communication channel.

This idea was discussed in the literature Stoyanovski et al. (1997); Dmitriev et al. (2000) and was tested in the case when the chaotic systems were one-dimensional maps Dmitriev et al. (2000). Here, on the example of two-dimensional maps we show that this approach can be used for synchronization of a higher-dimensional chaotic maps (both hyperbolic and non-hyperbolic).

As an example of two-dimensional maps the hyperbolic Lozi map Lozi (1978) is used in this paper. It is described by the equations

$`x_{n+1}`$ $`=`$ $`(\alpha 1)\alpha |x_n|+y_n,`$
$`y_{n+1}`$ $`=`$ $`\beta x_n,`$ (1)
where $`\alpha `$ and $`\beta `$ are parameters.

Non-hyperbolic maps are represented here by the Henon map Henon (1976)

$`x_{n+1}`$ $`=`$ $`1\alpha x_n^2+y_n,`$
$`y_{n+1}`$ $`=`$ $`\beta x_n,`$ (2)
## II Restrictions from Information Theory on Synchronization

Drive chaotic system is a specific source of information. With respect to information transmission, the driven system can be treated as a receiver of information, that, if synchronization takes place, receives all the information defining the state of the dynamical system, that is sent through the communication channel and continuously adjusts its dynamics in accordance with the information received.

Characteristic of a chaotic source are a finite rate of information production Billingsley (1965); Eckmann and Ruelle (1985) and continuous signal values. A question arises, what the necessary carrying capacity of a communication channel between the two systems is and how it relates to the possibility of high-quality synchronization.

According to Shannon’s theorem Shannon (1948), in order to transmit without errors information produced by the source at rate $`I`$ through a channel of capacity $`C`$ one must have

$$C>I.$$
(3)
Hence, for synchronization of the drive and response systems in the presence as well as in the absence of noise it is sufficient to have a communication channel with a carrying capacity larger than $`I`$. This fact has been noticed in Stoyanovski et al. (1997). It suggests that high-quality synchronization can be achieved, if external perturbations do not exceed some critical value.

The theorem also lays the basis for the quantitative analysis of the capacity of a noisy channel. For a channel with additive white gaussian noise, and bandwidth $`W`$ the capacity per unit of time is

$$C=W\mathrm{log}_2\frac{P+N}{N}.$$
(4)
where $`P`$ is the signal power and $`N`$ is the noise power.

Taking the sampling period at $`T=\frac{1}{2W}`$ so that the whole bandwidth is used, capacity per sample becomes

$$C=\frac{1}{2}\mathrm{log}_2\frac{P+N}{N},$$
(5)
Eq. (4) implies that when appropriate coding is used, information can be transmitted with the rate up to $`W\mathrm{log}_2\frac{P+N}{N}`$ bit/sec while error probability can be arbitrarily low.

Equation (4) also suggests that if the information production rate $`I`$ and the channel capacity are known, the maximum noise level can be calculated such that high-quality synchronization is still feasible.

As an example, if $`I`$ = 1 bit/sample, then, in theory, arbitrarily precise synchronization can be achieved when the ratio of the mean squared power of the chaotic signal $`P=<x_n^2>`$ to mean squared power of gaussian noise $`N=<w_n^2>`$ is

$$P/N>3.$$

The ”expense” of the possibility of high precision synchronization in the presence of noise is a special organization of the information transmitted through the channel and a certain time delay of the processes in the response system with respect to the drive system. Note also, that for the practical accomplishment of high-quality synchronization in the presence of noise a certain increase of the channel capacity is necessary compared to the value given by relation (3). Otherwise, the delay value will tend to infinity.

## III Hyperbolic Case. Lozi Map.

So, in order to be able to synchronize the response system with the drive system we should transmit information at a certain rate. Let us consider the information production of the Lozi map and the amount of information that must be transmitted for synchronization.

First, let us recall that for 1-D maps

$$x_{n+1}=f(x_n)$$
(6)
the average information production $`I`$, measured in bits per sample, can be expressed as the integral of (6) weighted with the invariant probability density $`P(x)`$

$$_0^1P(x)\mathrm{log}_2\left|\frac{df}{dx}\right|dx.$$
(7)
Relation (7) coincides with the definition of the Lyapunov exponent $`\lambda `$ of the one-dimensional map with the only difference that in the relation for the Lyapunov exponent the natural logarithm is used instead of the base-2 logarithm. Hence, the Lyapunov exponent for 1-D map can be treated as the information production rate expressed in base-$`e`$ units and it is equivalent to the Kolmogorov entropy $`h`$. In order to transform it to bit/sample, we multiply $`\lambda `$ by $`\mathrm{log}_2e`$. Let us remark that the Kolmogorov entropy $`h`$ and the information production rate $`R`$ are generally the same not only in the case of 1-D maps, but also in more general cases. However, it is common to express $`R`$ in bits/sample and $`h`$ in nats/sample.

The situation with information production in 2-D maps, e.g. in the Lozi map, is more complicated. It is well known Eckmann and Ruelle (1985) that for differentiable maps the following inequality between Kolmogorov entropy $`h`$ and positive Lyapunov exponents holds:

$$h\lambda _1+\lambda _2,$$
(8a)
if both Lyapunov exponents are positive, or
$$h\lambda _1,$$
(8b)
if only $`\lambda _1`$ is positive. Under some additional conditions inequalities (8) can turn into equalities. There are no similar results for the non-differentiable Lozi map. However, one can try to use another approach to estimate the information production by the Lozi map.

Let $`N_n`$ be the number of unstable periodic orbits of length $`n`$ in the chaotic attractor, and thus $`L_n=N_nn`$ the number of cyclical points. Then the following limit is supposed to estimate topological entropy

$$K_0=\underset{n\mathrm{}}{lim}\frac{1}{n}\mathrm{ln}L_n,$$
(9)
Estimates for information production $`I_n`$, calculated with the aid of (9) are presented in Table 1 for different $`n`$.

Both methods of estimating information production (including the method based on the positive Lyapunov exponents ) give similar results.

Fig. 1 shows the average information production for different values $`\alpha `$ and $`\beta `$. For $`\alpha =1.7`$; $`\beta =0.5`$ the average information production rate is $`I0.7`$ bits/sample.

However, information production differs from iteration to iteration. Fig. 2 shows the information production rate probability density function. As can be seen in the figure the rate never exceeds 1 bit/sample.

Consequently, to ensure synchronization a channel with capacity $`C>I=0.7`$ bits/sample can be used. However, it is desirable that the channel capacity should be at least $`C=I_{max}=1`$ bit/sample in order to take the maximum information production of each sample into account. Below a symbolic sequence for Lozi map is studied as an example of such a binary sequence.

Synchronization scheme

The proposed scheme is shown in Fig. 3. The signal $`x_n`$ produced by iteration of the Lozi map is transformed by a 2-level quantizer (threshold device) into a symbolic sequence $`X_n=\text{sign}(x_n)`$, i.e. into -1 if $`x_n<0`$ and into +1 if $`x_n0`$. Then this binary signal is sent through the channel, where it is corrupted by noise: $`z_n=X_n+w_n`$. The quantizer transforms it back to the binary signal $`\widehat{X}_n=\text{sign}(z_n)`$.

The $`\pm 1`$ values of binary sequence correspond to symbols $`L`$ and $`R`$ of the symbolic sequence. This symbolic sequence is used in the reconstruction block to restore the chaotic sequence. Thus, in the absence of noise, chaotic sequence reconstructed with a high precision is fed to the input of the response system, or an estimate of this chaotic sequence, if there is noise.

First, a problem with the noisefree case will be analyzed.

Reconstruction of a Trajectory from Symbolic Sequence

According to the synchronization scheme, at the input of the response system the incoming symbolic sequence must be used to reconstruct the chaotic sequence generated by the chaotic source.

In the case of one-dimensional maps reconstruction of the chaotic sequence based on the symbolic sequence can be accomplished by iterating the map backward Stoyanovski et al. (1997); Dmitriev et al. (2000). Since the map is stretching, being iterated backward it becomes contracting. Hence, repeatedly applying the inverse map to the initial conditions given by the elements of the symbolic sequence can give a good estimate of the chaotic sequence.

Consider a procedure of reconstruction of a chaotic sequence given the symbolic sequence for the case of Lozi map.

The Jacobian of (I) is constant and equals $`\beta `$. This means that the area of a small cell will be contracted by each iteration of the Lozi map by a factor $`\beta `$. But the distance between two close points increases in a certain direction, the stretching direction, at a rate determined by the positive Lyapunov exponent $`\lambda _1`$. Let two points in the plane be separated along the stretching direction by the small distance $`\delta _0`$ at time 0. Then the distance between the corresponding trajectories at moment $`m`$ is approximately

$$\delta x_m\delta _0\mathrm{exp}(\lambda _1m),$$
(10)
The situation is very similar to the case of the 1-D map, where one could use this property (10) of the map to improve our knowledge of the value of the trajectory at present on the basis of information about its values in the future. Namely, to improve the precision of $`x_n`$ the map should be iterated in reverse time beginning from $`x_{n+k}`$.

But what happens if we iterate the Lozi map in reverse time? In this case the area of a small cell will not decrease but increase. The direction corresponding to the positive Lyapunov exponent will be contracting but the direction corresponding to the negative Lyapunov exponent will be stretching. The trajectories will diverge again. The rate of this divergence will be determined by the absolute value of the second Lyapunov exponent.

The fact that two trajectories will diverge when the map is iterated either forward or backward can be written as

$$\delta x_m\delta _0\mathrm{exp}(\lambda _1m)+\epsilon _0\mathrm{exp}(\lambda _2m),$$
(11)
where $`\epsilon _0`$ is the initial distance between the two points in the direction of contraction. As follows from (11), in order to improve the knowledge about the position of the trajectory at the present time, it is necessary to use information both about the ”future” and the ”past” of the trajectory.

We rewrite equations (I) for the Lozi map in such a way as to make it contracting both from the future and from the past:

$$|x_n|=\frac{\alpha 1}{\alpha }\frac{1}{\alpha }x_{n+1}+\frac{\beta }{\alpha }x_{n1}.$$
(12)
Map (12) is a contracting map because coefficients $`1/\alpha `$ in front of $`x_{n+1}`$ and $`\beta /\alpha `$ in front of $`x_{n1}`$($`\alpha =1.7,\beta =0.5`$) as well as their sum are less than $`1`$. Contracting features of map (12) may be used to improve an estimate of the variable value at the $`n`$-th moment using information about the variable values at the ($`n1`$)-th and ($`n+1`$)-th moments. Note that map (12) is not single-valued but a double valued map.

Reconstruction algorithm. So, let us have a symbolic sequence $`X_1,\mathrm{}X_n,\mathrm{}X_{n+k},\mathrm{}X_N`$, where $`X_k\{1,1\}`$: $`N`$ is the number of elements in the sequence. We evaluate $`|x_n|`$ at the first step for all elements besides the first and the last, i.e. for $`n=2,\mathrm{},N1`$ in the following way

$$x_n^1=X_n|x_n^1|=X_n\left[\frac{\alpha 1}{\alpha }\frac{1}{\alpha }X_{n+1}+\frac{\beta }{\alpha }X_{n1}\right].$$
(13)
Elements of the symbolic sequence are used at this stage as initial approximation for the estimate. At the $`i`$-th step of the procedure the estimates obtained at the previous ($`i`$-1)-th step are used.

$$x_n^i=X_n|x_n^i|=X_n\left[\frac{\alpha 1}{\alpha }\frac{1}{\alpha }x_{n+1}^{i1}+\frac{\beta }{\alpha }x_{n1}^{i1}\right].$$
(14)
where $`n=2,\mathrm{},N1`$. We finish the process when the difference between estimates of $`x^i`$ on $`i`$-th and $`i+1`$-th iterations is less then some small $`\epsilon `$.

The results of chaotic sequence reconstruction using the above algorithm are presented in Fig. 4. The four curves in Fig. 4 correspond to the relative precision (in dB) obtained by taking $`N=10,40,70\text{ and }100`$ points of the symbolic sequence. Each of these curves looks as two sides of a triangle.

Consider the longest curve, that shows the results of the reconstruction of a fragment 100 points long. It can be seen that the first and the last points are not reconstructed at all, they are just the values of the symbolic sequence. The precision at these points corresponds to the precision of the initial approximation. The best result of reconstruction with precision $`10^{15}`$ corresponds to the region of 30-th point. The ratio of the number of points to the left and to the right from this point is 3:7 or 1:2.3 that is approximately the ratio of the coefficients $`1/\alpha `$ and $`\beta /\alpha `$ in (12): $`\beta /\alpha :1/\alpha =1:2`$

Hence, to reconstruct the sequence of chaotic signals $`x_1,\mathrm{}x_n`$ with a given precision , one first has to calculate the length of the fragment of the symbolic sequence to be used for reconstruction of one point of the chaotic sequence. For instance, the length of the fragment equals 100 when the reconstruction precision is $`10^{15}`$. Then, the left-edge fragment of the symbolic sequence $`X_1,\mathrm{}X_{100}`$ is used to reconstruct the 30th point of the chaotic sequence $`x_{30}`$. Then the fragment $`X_2,\mathrm{}X_{101}`$ is used to reconstruct the point $`x_{31}`$ of the chaotic sequence and so on. As for reconstruction of any given point of the chaotic sequence one needs 29 preceding and 70 following points of the corresponding symbolic sequence. Reconstruction can be accomplished with this precision only for those points that are non less then 29 positions distant from the left edge and 70 positions distant from the right one.

## IV Non-hyperbolic Henon Map

In the case of non-hyperbolic maps, e.g. the Henon map, the approach based on the transmission of the symbolic sequence with subsequent reconstruction of the chaotic sequence fails to be directly applicable. However, an attempt to apply this approach allows to understand why the results are insufficient and helps to develop a suitable method.

Assume first, as in the case of the Lozi map, that a sequence $`X_n=\text{sign}(x_n)`$ is transmitted through the channel. Note that the sequence $`x_1,\mathrm{}x_N,\mathrm{}`$ is not the symbolic sequence for this case.

Henon map can be rewritten as a one-dimensional map of the second order

$$x_{n+1}=1\alpha x_n^2+\beta x_{n1}.$$
(15)
When iterated forward, this map is stretching at almost all points of the trajectory, that is, the error in the value of $`x_{n+1}`$ usually is greater than that of $`x_n`$. On average, the distance between two close points increases exponentially with time.

Rewrite (15) in the form

$$x_n=\frac{1}{\sqrt{\alpha }}\sqrt{1x_{n+1}+\beta x_{n1}}.$$
(16)
Map (16) is contracting everywhere but in the region of small $`x_n`$: $`|x_n|<\epsilon `$, where $`\epsilon 0.1`$. Outside this region the error of the estimated value of $`x_n`$ according to (16) is smaller than the error of the estimates of $`x_{n1}`$ and $`x_{n+1}`$ that are used to get an estimate of $`x_n`$. For small $`|x_n|`$ this is not true, hence, the algorithm analogous to the one used for the Lozi map can not be used to reconstruct the chaotic sequence with high precision. A typical result of the application of this algorithm to the Henon map is shown in Fig. 5 (line 2). One can see that there are intervals with sharp reduction of reconstruction precision and the intervals where the precision of reconstruction is relatively high. Deterioration of the precision always occurs because of the lack of contracting properties of map (16) for small $`|x_n|`$.

Assume that at the reconstruction block the estimates of a chaotic sequence at the moments $`n_0`$ and $`n_0+1`$ are known with the desired precision and there is also a copy of the Henon map. Then this information is sufficient to get the values of the elements of the binary sequence $`X_n`$ for several points with the indices $`n>n_0`$. For this one just have to iterate the Henon map with initial conditions $`(x_{n_0},x_{n_01})`$ and construct a ”forecast”. This ”forecast” allows to determine the moments of time when the trajectory goes through a region of small absolute values.

Since initial conditions usually are known only with a finite precision, the correct values for the elements of the symbolic sequence can be obtained only for a relatively short part of the trajectory when the error of the ”forecast” is much less then the size of the attractor.

Above, in the description of the algorithm for Lozi map it has been noted that for a reconstruction of a chaotic sequence $`x_1,\mathrm{}x_N`$ with a high quality precesion it is sufficient to know the symbolic sequence $`X_n`$ for $`n[2,N1]`$ and $`x_1,x_N`$ with the desired precision. The same conditions hold for the case of Henon map given that in the range $`n[2,N1]`$ there are no $`x_n`$ with absolute values close to zero.

Consequently, we arrive at the following algorithm of the information transmission from the drive to the response system. Let $`\nu _i`$ be the indices of the points where the trajectory comes close to zero, $`\mu _i=[\nu _i,\nu _{i+1}]`$ \- the segment of a trajectory limited by two subsequent points close to zero (see Fig. 6). Assume that at the input of the driven system there is an estimate of the chaotic sequence for all points of $`\mu _i`$. The two last points from $`\mu _i`$ are taken as the initial conditions for the forecast of points from $`\mu _{i+1}`$. Note also that the length of $`\mu _{i+1}`$ is initially unknown at the response system side. Since the initial conditions for a forecasting trajectory are known with some error, a disturbed and undisturbed trajectories diverge exponentially and the precision of the forecast also grows exponentially with the distance from $`\nu _{i+1}`$. Nevertheless, if the length of $`\mu _{i+1}`$ is not very large, one can: (1) predict the index of point $`\nu _{i+2}`$ where the chaotic trajectory is close to zero and (2) construct the binary sequence $`X_n`$ for all points from $`\mu _{i+1}`$.

At this stage the only single datum needed for chaotic sequence reconstruction is the value at the point $`\nu _{i+2}`$. This value is transmitted through the channel with the necessary precision. After that $`\mu _{i+1}`$ is reconstructed with the aid of the algorithm described for the Lozi map. Hence, to reconstruct the chaotic sequence at all points of $`\mu _{i+1}`$ one only has to transmit the value of a single point (with the index $`\nu _{i+2}`$).

A subtle modification of this algorithm can substantially reduce the amount of information transmitted. The case is that the forecast for the points from $`\mu _{i+1}`$ allows to get some estimate for the point $`x_{\nu _{i+2}}`$, and so, there is no need to transmit the whole value of this point. One just needs to transmit the bits that can be distorted due to exponential divergence of the trajectories. Since the rate of divergence is solely determined by the first Lyapunov exponent, the amount of information to be transmitted through the communication channel is also determined only by this property of the chaotic map and is independent of the desired reconstruction precision of the chaotic sequence.

A numerical simulation of the proposed algorithm ensures high precision of synchronization with a volume of transmitted information $`1`$ bits/sample, that is close to the rate of information production by Henon map ($`0.6`$ bits/sample). Note that in Junge and Parlitz (2001) the method of synchronization with dynamical coupling was analyzed that allows to reduce the amount of necessary information to be transmitted for synchronization by a factor of 5-6 as compared to conventional procedure. The approach considered above provides a reduction of information flow by a factor of 20-30 in comparison with conventional procedure.

## V Synchronization in the Presence of Noise

It has been shown that in order to achieve synchronization of hyperbolic as well as non-hyperbolic maps it is sufficient to transmit information contained in the chaotic sequence and then utilize this information to reconstruct the chaotic sequence. The precision of reconstruction depends on the length of the sequence and on the number of elements of the symbolic sequence that are directly used to reconstruct the chaotic sample. The reconstructed sequence of samples ensures high-quality synchronization of drive and response systems.

If binary information is transmitted via a noisy channel errors may appear in the binary sequence. These errors may lead to incorrect reconstruction of the chaotic signal and thus reduce the synchronization precision.

Consider the results of numerical simulation of the precision of synchronization of chaotic signal reconstruction after transmission through a noisy channel. Note that errors can be made arbitrarily small by increasing the channel capacity (e.g., by means of using error correcting codes). Hence, synchronization through channels with a capacity close to the minimum is of greater concern.

Fig. 7 shows graphs that illustrate the quality of synchronization when information is transmitted through a channel with gaussian noise.

It can be seen that for signal to noise ratios up to about 7.5 dB, the synchronization error is actually given by the noise and it cannot be improved by increasing the number of points used for the reconstruction of a sample. Above this threshold, the synchronization error is decreased by about 4.2 dB/points used in the reconstruction, which is in good agreement with the rate of information production $`I`$ of 0.7 bit/sample.

Similar results were obtained for the synchronization of Henon maps.

## VI Conclusion

In this paper a synchronization scheme for two-dimensional maps is considered that is based on transmission of information about the state of drive system by unidirectional coupling. It is shown that the necessary amount of information that must be delivered to the response system is determined by the rate of information production by the dynamical system.

When this threshold is increased, however, arbitrarily precise synchronization can be achieved. The only price to pay for that is the complexity of the reconstruction algorithm and the delay of the reconstructed signal. This is contrary to the common belief that the synchronization error necessarily monotonically increases with the noise.

The schemes of synchronization of two-dimensional maps are presented, that are based on reconstruction of the chaotic sequence. Their stability with respect to noise almost coincides with the theoretical estimate of the ultimate limit.

###### Acknowledgements.

This work has been supported by the Swiss National Science Foundation, SCOPES project Nr. 75SUPJ062310.


text:
# Untitled Document

ADDENDUM

In the article Gen. Rel. Grav. 32, 1633 (2000), by J. G. Pereira and C. M. Zhang (here referred as Paper I), the special relativity energy-momentum tensor was used to discuss the neutrino phase-splitting in a weak gravitational field. However, it would be more appropriate to use the general relativity energy-momentum tensor. When we do that, as we are going to see, some results change, but the basic conclusion remains the same.

The ratio between the two terms in the right-hand side of Eq.(6) of Paper I can be written as

$$\xi =\frac{|h_{\mu \nu }dx^\mu dx^\nu |}{(ds^o)^2}=\frac{\alpha \delta _{\mu \nu }dx^\mu dx^\nu }{(ds^o)^2}=\frac{\alpha \delta _{\mu \nu }dx^\mu dx^\nu }{ds^2}\frac{ds^2}{(ds^o)^2}.$$
(1)
As

$$\frac{ds}{ds^o}=\sqrt{1\xi },$$
(2)
we have consequently

$$\xi =\frac{\alpha }{m^2}(1\xi )[(P^o)^2+(P^r)^2],$$
(3)
where the momentum is defined by $`P^\mu =m(dx^\mu /ds)`$, with $`(P^r)^2=(P^x)^2+(P^y)^2+(P^z)^2`$. Therefore, we get

$$\xi =\frac{\alpha (2\gamma ^21)}{1+\alpha (2\gamma ^21)},$$
(4)
where $`\gamma =(P^o/m)`$ is the relativistic factor. The approximate mass-shell condition $`(P^o)^2(P^r)^2m^2`$ has been used in the above expression.

The possible values of $`\xi `$ is restricted to the range $`0\xi 1`$, where the values 0 and 1 represent respectively the vacuum and the null cases. In the absence of gravitational field, which corresponds to $`\alpha 0`$, we find $`\xi =0`$, and the vacuum situation is recovered. When $`vc`$, which corresponds to an ultra relativistic case, $`\gamma \mathrm{}`$, and we obtain $`\xi =1`$. We see from Eq.(4), therefore, that in fact $`0\xi 1`$ in any situation.

We can now discuss the expansion conditions. For a low-energy object, as for example a thermal neutron in the laboratory whose typical velocity is $`v^210^{10}`$, we have $`\gamma 1`$, and consequently

$$\xi =\frac{\alpha }{1+\alpha }\frac{r_s}{r}1.$$
(5)
This is the conventional weak-field condition, which means that the phase splitting can be performed. On the other hand, for ultra-relativistic massive neutrinos, the relativistic factor is $`\gamma ^210^{12}`$, and in the case of the Earth gravitational potential, for which $`(r_s/r)10^{11}`$, we get $`\xi =0.951`$. Consequently, for these particles, the phase splitting represented by Eq.(2) of Paper I cannot be performed. Therefore, when the general relativity energy-momentum tensor is used, despite some numerical differences in the values assumed by $`\xi `$, the basic conclusion of Paper I remains valid.

The authors would like to thank G. F. Rubilar for valuable comments. They would like also to thank CNPq-Brazil and FAPESP-Brazil for financial support.


text:
# NLTK: The Natural Language Toolkit

## 1 Introduction

Teachers of introductory courses on computational linguistics are often faced with the challenge of setting up a practical programming component for student assignments and projects. This is a difficult task because different computational linguistics domains require a variety of different data structures and functions, and because a diverse range of topics may need to be included in the syllabus.

A widespread practice is to employ multiple programming languages, where each language provides native data structures and functions that are a good fit for the task at hand. For example, a course might use Prolog for parsing, Perl for corpus processing, and a finite-state toolkit for morphological analysis. By relying on the built-in features of various languages, the teacher avoids having to develop a lot of software infrastructure.

An unfortunate consequence is that a significant part of such courses must be devoted to teaching programming languages. Further, many interesting projects span a variety of domains, and would require that multiple languages be bridged. For example, a student project that involved syntactic parsing of corpus data from a morphologically rich language might involve all three of the languages mentioned above: Perl for string processing; a finite state toolkit for morphological analysis; and Prolog for parsing. It is clear that these considerable overheads and shortcomings warrant a fresh approach.

Apart from the practical component, computational linguistics courses may also depend on software for in-class demonstrations. This context calls for highly interactive graphical user interfaces, making it possible to view program state (e.g. the chart of a chart parser), observe program execution step-by-step (e.g. execution of a finite-state machine), and even make minor modifications to programs in response to “what if” questions from the class. Because of these difficulties it is common to avoid live demonstrations, and keep classes for theoretical presentations only. Apart from being dull, this approach leaves students to solve important practical problems on their own, or to deal with them less efficiently in office hours.

In this paper we introduce a new approach to the above challenges, a streamlined and flexible way of organizing the practical component of an introductory computational linguistics course. We describe NLTK, the Natural Language Toolkit, which we have developed in conjunction with a course we have taught at the University of Pennsylvania.

The Natural Language Toolkit is available under an open source license from http://nltk.sf.net/. NLTK runs on all platforms supported by Python, including Windows, OS X, Linux, and Unix.

## 2 Choice of Programming Language

The most basic step in setting up a practical component is choosing a suitable programming language. A number of considerations influenced our choice. First, the language must have a shallow learning curve, so that novice programmers get immediate rewards for their efforts. Second, the language must support rapid prototyping and a short develop/test cycle; an obligatory compilation step is a serious detraction. Third, the code should be self-documenting, with a transparent syntax and semantics. Fourth, it should be easy to write structured programs, ideally object-oriented but without the burden associated with languages like C++. Finally, the language must have an easy-to-use graphics library to support the development of graphical user interfaces.

In surveying the available languages, we believe that Python offers an especially good fit to the above requirements. Python is an object-oriented scripting language developed by Guido van Rossum and available on all platforms (www.python.org). Python offers a shallow learning curve; it was designed to be easily learnt by children \[van Rossum, 1999\]. As an interpreted language, Python is suitable for rapid prototyping. Python code is exceptionally readable, and it has been praised as “executable pseudocode.” Python is an object-oriented language, but not punitively so, and it is easy to encapsulate data and methods inside Python classes. Finally, Python has an interface to the Tk graphics toolkit \[Lundh, 1999\], and writing graphical interfaces is straightforward.

## 3 Design Criteria

Several criteria were considered in the design and implementation of the toolkit. These design criteria are listed in the order of their importance. It was also important to decide what goals the toolkit would *not* attempt to accomplish; we therefore include an explicit set of non-requirements, which the toolkit is not expected to satisfy.

### 3.1 Requirements

##### Ease of Use.

The primary purpose of the toolkit is to allow students to concentrate on building natural language processing (NLP) systems. The more time students must spend learning to use the toolkit, the less useful it is.

##### Consistency.

The toolkit should use consistent data structures and interfaces.

##### Extensibility.

The toolkit should easily accommodate new components, whether those components replicate or extend the toolkit’s existing functionality. The toolkit should be structured in such a way that it is obvious where new extensions would fit into the toolkit’s infrastructure.

##### Documentation.

The toolkit, its data structures, and its implementation all need to be carefully and thoroughly documented. All nomenclature must be carefully chosen and consistently used.

##### Simplicity.

The toolkit should structure the complexities of building NLP systems, not hide them. Therefore, each class defined by the toolkit should be simple enough that a student could implement it by the time they finish an introductory course in computational linguistics.

##### Modularity.

The interaction between different components of the toolkit should be kept to a minimum, using simple, well-defined interfaces. In particular, it should be possible to complete individual projects using small parts of the toolkit, without worrying about how they interact with the rest of the toolkit. This allows students to learn how to use the toolkit incrementally throughout a course. Modularity also makes it easier to change and extend the toolkit.

### 3.2 Non-Requirements

##### Comprehensiveness.

The toolkit is not intended to provide a comprehensive set of tools. Indeed, there should be a wide variety of ways in which students can extend the toolkit.

##### Efficiency.

The toolkit does not need to be highly optimized for runtime performance. However, it should be efficient enough that students can use their NLP systems to perform real tasks.

##### Cleverness.

Clear designs and implementations are far preferable to ingenious yet indecipherable ones.

## 4 Modules

The toolkit is implemented as a collection of independent *modules*, each of which defines a specific data structure or task.

A set of core modules defines basic data types and processing systems that are used throughout the toolkit. The token module provides basic classes for processing individual elements of text, such as words or sentences. The tree module defines data structures for representing tree structures over text, such as syntax trees and morphological trees. The probability module implements classes that encode frequency distributions and probability distributions, including a variety of statistical smoothing techniques.

The remaining modules define data structures and interfaces for performing specific NLP tasks. This list of modules will grow over time, as we add new tasks and algorithms to the toolkit.

### Parsing Modules

The parser module defines a high-level interface for producing trees that represent the structures of texts. The chunkparser module defines a sub-interface for parsers that identify non-overlapping linguistic groups (such as base noun phrases) in unrestricted text.

Four modules provide implementations for these abstract interfaces. The srparser module implements a simple shift-reduce parser. The chartparser module defines a flexible parser that uses a *chart* to record hypotheses about syntactic constituents. The pcfgparser module provides a variety of different parsers for probabilistic grammars. And the rechunkparser module defines a transformational regular-expression based implementation of the chunk parser interface.

### Tagging Modules

The tagger module defines a standard interface for augmenting each token of a text with supplementary information, such as its part of speech or its WordNet synset tag; and provides several different implementations for this interface.

### Finite State Automata

The fsa module defines a data type for encoding finite state automata; and an interface for creating automata from regular expressions.

### Type Checking

Debugging time is an important factor in the toolkit’s ease of use. To reduce the amount of time students must spend debugging their code, we provide a type checking module, which can be used to ensure that functions are given valid arguments. The type checking module is used by all of the basic data types and processing classes.

Since type checking is done explicitly, it can slow the toolkit down. However, when efficiency is an issue, type checking can be easily turned off; and with type checking is disabled, there is no performance penalty.

### Visualization

Visualization modules define graphical interfaces for viewing and manipulating data structures, and graphical tools for experimenting with NLP tasks. The draw.tree module provides a simple graphical interface for displaying tree structures. The draw.tree\_edit module provides an interface for building and modifying tree structures. The draw.plot\_graph module can be used to graph mathematical functions. The draw.fsa module provides a graphical tool for displaying and simulating finite state automata. The draw.chart module provides an interactive graphical tool for experimenting with chart parsers.

The visualization modules provide interfaces for interaction and experimentation; they do not directly implement NLP data structures or tasks. Simplicity of implementation is therefore less of an issue for the visualization modules than it is for the rest of the toolkit.

### Text Classification

The classifier module defines a standard interface for classifying texts into categories. This interface is currently implemented by two modules. The classifier.naivebayes module defines a text classifier based on the Naive Bayes assumption. The classifier.maxent module defines the maximum entropy model for text classification, and implements two algorithms for training the model: Generalized Iterative Scaling and Improved Iterative Scaling.

The classifier.feature module provides a standard encoding for the information that is used to make decisions for a particular classification task. This standard encoding allows students to experiment with the differences between different text classification algorithms, using identical feature sets.

The classifier.featureselection module defines a standard interface for choosing which features are relevant for a particular classification task. Good feature selection can significantly improve classification performance.

## 5 Documentation

The toolkit is accompanied by extensive documentation that explains the toolkit, and describes how to use and extend it. This documentation is divided into three primary categories:

##### Tutorials

teach students how to use the toolkit, in the context of performing specific tasks. Each tutorial focuses on a single domain, such as tagging, probabilistic systems, or text classification. The tutorials include a high-level discussion that explains and motivates the domain, followed by a detailed walk-through that uses examples to show how NLTK can be used to perform specific tasks.

##### Reference Documentation

provides precise definitions for every module, interface, class, method, function, and variable in the toolkit. It is automatically extracted from docstring comments in the Python source code, using Epydoc \[Loper, 2002\].

##### Technical Reports

explain and justify the toolkit’s design and implementation. They are used by the developers of the toolkit to guide and document the toolkit’s construction. Students can also consult these reports if they would like further information about how the toolkit is designed, and why it is designed that way.

## 6 Uses of NLTK

### 6.1 Assignments

NLTK can be used to create student assignments of varying difficulty and scope. In the simplest assignments, students experiment with an existing module. The wide variety of existing modules provide many opportunities for creating these simple assignments. Once students become more familiar with the toolkit, they can be asked to make minor changes or extensions to an existing module. A more challenging task is to develop a new module. Here, NLTK provides some useful starting points: predefined interfaces and data structures, and existing modules that implement the same interface.

#### Example: Chunk Parsing

As an example of a moderately difficult assignment, we asked students to construct a chunk parser that correctly identifies base noun phrase chunks in a given text, by defining a cascade of transformational chunking rules. The NLTK rechunkparser module provides a variety of regular-expression based rule types, which the students can instantiate to construct complete rules. For example, ChunkRule(’\<NN.\*\>’) builds chunks from sequences of consecutive nouns; ChinkRule(’\<VB.\>’) excises verbs from existing chunks; SplitRule(’\<NN\>’, ’\<DT\>’) splits any existing chunk that contains a singular noun followed by determiner into two pieces; and MergeRule(’\<JJ\>’, ’\<JJ\>’) combines two adjacent chunks where the first chunk ends and the second chunk starts with adjectives.

The chunking tutorial motivates chunk parsing, describes each rule type, and provides all the necessary code for the assignment. The provided code is responsible for loading the chunked, part-of-speech tagged text using an existing tokenizer, creating an unchunked version of the text, applying the chunk rules to the unchunked text, and scoring the result. Students focus on the NLP task only – providing a rule set with the best coverage.

In the remainder of this section we reproduce some of the cascades created by the students. The first example illustrates a combination of several rule types:

```
cascade = [
  ChunkRule(’<DT><NN.*><VB.><NN.*>’),
  ChunkRule(’<DT><VB.><NN.*>’),
  ChunkRule(’<.*>’),
  UnChunkRule(’<IN|VB.*|CC|MD|RB.*>’),
  UnChunkRule("<,|\\.|‘‘|’’>"),
  MergeRule(’<NN.*|DT|JJ.*|CD>’,
            ’<NN.*|DT|JJ.*|CD>’),
  SplitRule(’<NN.*>’, ’<DT|JJ>’)
]

```

The next example illustrates a brute-force statistical approach. The student calculated how often each part-of-speech tag was included in a noun phrase. They then constructed chunks from any sequence of tags that occurred in a noun phrase more than 50% of the time.

```
cascade = [
  ChunkRule(’<\\$|CD|DT|EX|PDT
             |PRP.*|WP.*|\\#|FW
             |JJ.*|NN.*|POS|RBS|WDT>*’)
]

```

In the third example, the student constructed a single chunk containing the entire text, and then excised all elements that did not belong.

```
cascade = [
  ChunkRule(’<.*>+’)
  ChinkRule(’<VB.*|IN|CC|R.*|MD|WRB|TO|.|,>+’)
]

```

### 6.2 Class demonstrations

NLTK provides graphical tools that can be used in class demonstrations to help explain basic NLP concepts and algorithms. These interactive tools can be used to display relevant data structures and to show the step-by-step execution of algorithms. Both data structures and control flow can be easily modified during the demonstration, in response to questions from the class.

Since these graphical tools are included with the toolkit, they can also be used by students. This allows students to experiment at home with the algorithms that they have seen presented in class.

#### Example: The Chart Parsing Tool

The chart parsing tool is an example of a graphical tool provided by NLTK. This tool can be used to explain the basic concepts behind chart parsing, and to show how the algorithm works. Chart parsing is a flexible parsing algorithm that uses a data structure called a *chart* to record hypotheses about syntactic constituents. Each hypothesis is represented by a single *edge* on the chart. A set of *rules* determine when new edges can be added to the chart. This set of rules controls the overall behavior of the parser (e.g., whether it parses top-down or bottom-up).

The chart parsing tool demonstrates the process of parsing a single sentence, with a given grammar and lexicon. Its display is divided into three sections: the bottom section displays the chart; the middle section displays the sentence; and the top section displays the partial syntax tree corresponding to the selected edge. Buttons along the bottom of the window are used to control the execution of the algorithm. The main display window for the chart parsing tool is shown in Figure 1.

This tool can be used to explain several different aspects of chart parsing. First, it can be used to explain the basic chart data structure, and to show how edges can represent hypotheses about syntactic constituents. It can then be used to demonstrate and explain the individual rules that the chart parser uses to create new edges. Finally, it can be used to show how these individual rules combine to find a complete parse for a given sentence.

To reduce the overhead of setting up demonstrations during lecture, the user can define a list of preset charts. The tool can then be reset to any one of these charts at any time.

The chart parsing tool allows for flexible control of the parsing algorithm. At each step of the algorithm, the user can select which rule or strategy they wish to apply. This allows the user to experiment with mixing different strategies (e.g., top-down and bottom-up). The user can exercise fine-grained control over the algorithm by selecting which edge they wish to apply a rule to. This flexibility allows lecturers to use the tool to respond to a wide variety of questions; and allows students to experiment with different variations on the chart parsing algorithm.

### 6.3 Advanced Projects

NLTK provides students with a flexible framework for advanced projects. Typical projects involve the development of entirely new functionality for a previously unsupported NLP task, or the development of a complete system out of existing and new modules.

The toolkit’s broad coverage allows students to explore a wide variety of topics. In our introductory computational linguistics course, topics for student projects included text generation, word sense disambiguation, collocation analysis, and morphological analysis.

NLTK eliminates the tedious infrastructure-building that is typically associated with advanced student projects by providing students with the basic data structures, tools, and interfaces that they need. This allows the students to concentrate on the problems that interest them.

The collaborative, open-source nature of the toolkit can provide students with a sense that their projects are meaningful contributions, and not just exercises. Several of the students in our course have expressed interest in incorporating their projects into the toolkit.

Finally, many of the modules included in the toolkit provide students with good examples of what projects should look like, with well thought-out interfaces, clean code structure, and thorough documentation.

#### Example: Probabilistic Parsing

The probabilistic parsing module was created as a class project for a statistical NLP course. The toolkit provided the basic data types and interfaces for parsing. The project extended these, adding a new probabilistic parsing interface, and using subclasses to create a probabilistic version of the context free grammar data structure. These new components were used in conjunction with several existing components, such as the chart data structure, to define two implementations of the probabilistic parsing interface. Finally, a tutorial was written that explained the basic motivations and concepts behind probabilistic parsing, and described the new interfaces, data structures, and parsers.

## 7 Evaluation

We used NLTK as a basis for the assignments and student projects in CIS-530, an introductory computational linguistics class taught at the University of Pennsylvania. CIS-530 is a graduate level class, although some advanced undergraduates were also enrolled. Most students had a background in either computer science or linguistics (and occasionally both). Students were required to complete five assignments, two exams, and a final project. All class materials are available from the course website http://www.cis.upenn.edu/~cis530/.

The experience of using NLTK was very positive, both for us and for the students. The students liked the fact that they could do interesting projects from the outset. They also liked being able to run everything on their computer at home. The students found the extensive documentation very helpful for learning to use the toolkit. They found the interfaces defined by NLTK intuitive, and appreciated the ease with which they could combine different components to create complete NLP systems.

We did encounter a few difficulties during the semester. One problem was finding large clean corpora that the students could use for their assignments. Several of the students needed assistance finding suitable corpora for their final projects. Another issue was the fact that we were actively developing NLTK during the semester; some modules were only completed one or two weeks before the students used them. As a result, students who worked at home needed to download new versions of the toolkit several times throughout the semester. Luckily, Python has extensive support for installation scripts, which made these upgrades simple. The students encountered a couple of bugs in the toolkit, but none were serious, and all were quickly corrected.

## 8 Other Approaches

The computational component of computational linguistics courses takes many forms. In this section we briefly review a selection of approaches, classified according to the (original) target audience.

Linguistics Students. Various books introduce programming or computing to linguists. These are elementary on the computational side, providing a gentle introduction to students having no prior experience in computer science. Examples of such books are: *Using Computers in Linguistics* \[Lawler and Dry, 1998\], and *Programming for Linguistics: Java Technology for Language Researchers* \[Hammond, 2002\].

Grammar Developers. Infrastructure for grammar development has a long history in unification-based (or constraint-based) grammar frameworks, from DCG \[Pereira and Warren, 1980\] to HPSG \[Pollard and Sag, 1994\]. Recent work includes \[Copestake, 2000, Baldridge et al., 2002a\]. A concurrent development has been the finite state toolkits, such as the Xerox toolkit \[Beesley and Karttunen, 2002\]. This work has found widespread pedagogical application.

Other Researchers and Developers. A variety of toolkits have been created for research or R&D purposes. Examples include the *CMU-Cambridge Statistical Language Modeling Toolkit* \[Clarkson and Rosenfeld, 1997\], the *EMU Speech Database System* \[Harrington and Cassidy, 1999\], the *General Architecture for Text Engineering* \[Bontcheva et al., 2002\], the *Maxent Package for Maximum Entropy Models* \[Baldridge et al., 2002b\], and the *Annotation Graph Toolkit* \[Maeda et al., 2002\]. Although not originally motivated by pedagogical needs, all of these toolkits have pedagogical applications and many have already been used in teaching.

## 9 Conclusions and Future Work

NLTK provides a simple, extensible, uniform framework for assignments, projects, and class demonstrations. It is well documented, easy to learn, and simple to use. We hope that NLTK will allow computational linguistics classes to include more hands-on experience with using and building NLP components and systems.

NLTK is unique in its combination of three factors. First, it was deliberately designed as courseware and gives pedagogical goals primary status. Second, its target audience consists of both linguists and computer scientists, and it is accessible and challenging at many levels of prior computational skill. Finally, it is based on an object-oriented scripting language supporting rapid prototyping and literate programming.

We plan to continue extending the breadth of materials covered by the toolkit. We are currently working on NLTK modules for Hidden Markov Models, language modeling, and tree adjoining grammars. We also plan to increase the number of algorithms implemented by some existing modules, such as the text classification module.

Finding suitable corpora is a prerequisite for many student assignments and projects. We are therefore putting together a collection of corpora containing data appropriate for every module defined by the toolkit.

NLTK is an open source project, and we welcome any contributions. Readers who are interested in contributing to NLTK, or who have suggestions for improvements, are encouraged to contact the authors.

## 10 Acknowledgments

We are indebted to our students for feedback on the toolkit, and to anonymous reviewers, Jee Bang, and the workshop organizers for comments on an earlier version of this paper. We are grateful to Mitch Marcus and the Department of Computer and Information Science at the University of Pennsylvania for sponsoring the work reported here.