Enhanced Packages in Maple 9: Part 2
Maple 9 contains many enhancements to existing packages. For additional enhancements, see Enhanced Packages in Maple 9: Part 1.
For information on new Maple 9 packages, see New Packages in Maple 9.
Enhanced Packages in Maple 9: Part 2 contains information for the following packages.
The StringTools package contains many new procedures. Many existing StringTools commands have been improved.
Metrics and Distances
Several new string metrics are provided: StringTools[HammingDistance], StringTools[EditDistance], StringTools[PrefixDistance], StringTools[SuffixDistance], and StringTools[SimilarityCoefficient].
with( StringTools ):
HammingDistance( "Mathematics", "Mathematische" );
EditDistance( "Mathematics", "Mathematische" );
PrefixDistance( "Mathematics", "Mathematische" );
SuffixDistance( "Mathematics", "Mathematische" );
SimilarityCoefficient( "Mathematics", "Mathematische" );
The Search and SearchAll pattern matching routines have been extended to allow simultaneous searching of multiple texts. By amortizing the cost of preprocessing, this is more efficient than composing single calls to Search using map2.
Pattern := Random( 1000, 'lower' ):
Texts := [seq]( Random( 5000, 'lower' ), i = 1 .. 5000 ):
evalb( Search( Pattern, Texts ) = map2( Search, Pattern, Texts ) );
time( Search( Pattern, Texts ) );
time( map2( Search, Pattern, Texts ) );
Texts := 'Texts':
In addition, you can perform multiple pattern searches on a single text.
SearchAll( [ "bac", "ab" ], "abcdababacef" );
P := [seq]( ThueMorse( i ), i = 5 .. 10 );
SearchAll( P, Random( 200, 'binary' ) );
You can perform multiple pattern searches for persistent pattern lists using the PatternDictionary subpackage, which exports procedures designed to manage a persistent (external) search data structure for a list of patterns. You can also perform multiple pattern matching repeatedly without incurring the costs of pattern preprocessing, something not possible using only Search and SearchAll. You can create a dictionary using the PatternDictionary[Create] constructor. The input word list is preprocessed once and can then be used for all subsequent searches using PatternDictionary[Search]. Using the PatternDictionary[Get] and PatternDictionary[Size] procedures, you can retrieve matching patterns from the dictionary.
ReadWordList := fname -> remove( type, StringTools:-Split( readbytes( fname, 'TEXT', infinity ) ), "" ):
DICT := PatternDictionary:-Create( ReadWordList( "/usr/share/dict/words" ) ):
PatternDictionary:-Size( DICT );
PatternDictionary:-Get( DICT, 666 );
PatternDictionary:-Search( DICT, "childbirth" );
map2( PatternDictionary:-Get, DICT, map2( op, 2, [ (15) ] ) );
The PatternDictionary subpackage also contains an algorithm for factoring a string over a dictionary of patterns. Given a string s, and a dictionary dict, the procedure PatternDictionary[Factors] computes a factorization of s over dict, that is, a sequence of patterns from dict whose concatenation is the string s.
dict := PatternDictionary:-Create( 'builtin' ):
PatternDictionary:-Factors( "linearalgebra", dict );
Using the new WildcardMatch tool, you can perform glob-style pattern matching. The pattern language is similar to that used in UNIX shells, and is commonly applied to file and directory listings.
WildcardMatch( "a*b", "accccb" );
WildcardMatch( "a[c-z]b", "acccc" );
WildcardMatch( "a[c-z]??b", "acccc" );
WildcardMatch( "a[c-z]??b", "acccb" );
select( curry( WildcardMatch, "maple.???" ), listdir( `if`( nops( [ libname ] ) = 1, libname, libname[ 1 ] ) ) );
Using the new RegSplit procedure, you can split a string on substrings matching a regular expression.
RegSplit( "(a|b)+", "xabyazbaabubav" );
Using the StringTools[RegSub] procedure, you can perform regular expression substitutions in strings. However, it has proved awkward to use in typical applications, and too closely matched the C APIs upon which it is based. A new StringTools[RegSubs] procedure is an improved user interface to this functionality. The calling interface resembles the built-in subs command.
RegSubs( "b" = "&&&", "abc" );
RegSubs( "[ \t]+" = " ", "Some text \twith\t\t too much white space. " );
Some text with too much white space.
Four new procedures support approximate pattern matching, that is, searching text with errors. Two error models are supported. Approximate searching with respect to the Hamming metric using the StringTools[HammingSearch] and StringTools[HammingSearchAll] procedures. These are analogous to Search and SearchAll, respectively, but take a third argument, a non-negative integer, which specifies the maximum allowable number of mismatches (the Hamming distance) in a match. Similarly, StringTools[ApproximateSearch] and StringTools[ApproximateSearchAll] perform approximate pattern matching using the edit (Levenshtein) distance as the metric of ``closeness'' of a match.
Search( "maths", "mathematical" );
HammingSearch( "maths", "mathematical", 1 );
ApproximateSearch( "maths", "mathematical", 1 ); # reports END of match
You can test whether one string is a subsequence of another using the new StringTools[IsSubSequence] procedure.
IsSubSequence( "abc", "abracadabra" );
A number of string comparisons can be performed based on n-grams, using the new StringTools[NGrams] routine.
NGrams( "abracadabra", 2 ) ; # 2-grams or digrams
nops( (30) ) / nops( convert( (30), 'set' ) );
NGrams( "abracadabra", 3 ) ; # 3-grams or trigrams
nops( (32) ) / nops( convert( (32), 'set' ) );
Manipulating English Text
An implementation of Porter's stemming algorithm is provided in the new Stem procedure.
Stem( "hopeful" );
Other routines designed to operate on natural language (especially English) text are StringTools[Words], StringTools[WordCount], StringTools[Metaphone], and StringTools[SyllableLength].
Words( "Dimension implies direction, implies measurement, implies the more and the less." ); # - Edwin E. Abbot, "Flatland"
WordCount( "Dimension implies direction, implies measurement, implies the more and the less." );
Metaphone( "Cline" );
Metaphone( "Kline" );
The value that SyllableLength returns does not match the lexical syllable length found in dictionaries for some words.
SyllableLength( "antidisestablishmentarianism" );
A number of procedures are now provided for combinatorial operations on strings.
The Permute procedure applies an arbitrary permutation to the characters comprising a string. This defines an action of the symmetric group of degree n on strings of length n.
Permute( "abc", [ 1, 3, 2 ] );
Two special cases are provided in the procedures Rotate and Exchange. The former applies a permutation of the form 123...n to a string of length n, and the latter applies a transposition permutation to a string.
seq( Rotate( "abc", i ), i = -3 .. 3 );
Exchange( "abc", 1, 3 );
The characters (actually, byte code points) of a string can be simultaneously shifted by a fixed quantity using the Shift procedure. This is essentially a generalized Caesar cipher.
Shift( "abc", 2 );
Shift( "abc", -1 );
All strings of a given length on a fixed set of characters can be produced using the Generate procedure. Specify the length of strings to produce and the ``alphabet'' upon which to generate the strings. Because of the rapid growth in the numbers of strings with the length and alphabet size, it is only practical to use this for modest sized inputs.
Generate( 3, "abc" );
The Repeat procedure implements iterated concatenation efficiently.
Repeat( "some text ", 4 );
some text some text some text some text
The Support utility determines the set of characters that occur in a string.
Support( "foobar" );
Analogous to the numboccur procedure, the NumbOccur procedure in the StringTools package counts the number of occurrences of a character in a string.
seq( NumbOccur( "foobar", ch ), ch = Support( "foobar" ) );
The Trim, TrimLeft, and TrimRight procedures remove leading and trailing whitespace from strings. The new Center, PadLeft, and PadRight procedures provide approximate inverses to these text operations by adding leading and trailing whitespace to strings. You must specify a width as the second argument to each of these routines.
PadLeft( "foo", 10 );
PadRight( "foo", 10 );
Center( "foo", 10 );
Combinatorics on Words
A number of new procedures support investigations in combinatorics on words (represented as strings).
Initial segments of the Thue-Morse and Fibonacci (semi-infinite) words can be constructed using StringTools[ThueMorse] and StringTools[Fibonacci], respectively.
seq( ThueMorse( n ), n = 1 .. 10 );
seq( Fibonacci( n ), n = 1 .. 5 );
map( length, [ (53) ] );
You can determine primitivity using StringTools[IsPrimitive]. You can extract the primitive root of a word using StringTools[PrimitiveRoot].
IsPrimitive( "abc" );
IsPrimitive( "ababab" );
PrimitiveRoot( "abc" );
PrimitiveRoot( "ababab" );
You can test for conjugacy in the free semigroup (on the nonzero byte values less than 256) using StringTools[IsConjugate]. You can also efficiently compute the (lexicographically) minimal element in the conjugacy class of a given word using StringTools[MinimumConjugate].
IsConjugate( "bca", "abc" );
IsConjugate( "bac", "abc" );
MinimumConjugate( "bca" );
MinimumConjugate( "bac" );
Every string possesses a unique non-increasing factorization into substrings, each of which is a minimum conjugate. These factors are the Lyndon factors of the string. You can compute this factorization using the procedure StringTools[LyndonFactors].
L := LyndonFactors( Fibonacci( 8 ) );
cat( op( L ) );
Fibonacci( 8 );
evalb( (65) = (64) );
andmap( w -> evalb( w = MinimumConjugate( w ) ), L );
seq( evalb( L[ i ] <= L[ i - 1 ] ), i = 2 .. nops( L ) );
You can also factor a word into monotonic factors using MonotonicFactors.
MonotonicFactors( Fibonacci( 8 ) );
andmap( IsMonotonic, (69) );
You can identify palindromes using the StringTools[IsPalindrome] procedure. (A palindrome is a string s for which s=Reverse⁡s.)
IsPalindrome( "abc" );
IsPalindrome( "aba" );
Periodicity of words (strings) plays an important role in combinatorics on words, as well as in pattern matching. A positive integer k is a period of a string s if si=si+k, for i=1..n−k, where n is the length of s. You can test whether k is a period of s using the StringTools[IsPeriod] procedure. The least period of a string s is the period of s. You can compute the period of a string using the StringTools[Period] procedure.
IsPeriod( "abcab", 2 );
IsPeriod( "abcab", 3 );
Period( "abcab" );
Period( "abcde" );
You can compute the length of the maximum overlap between two strings using the StringTools[Overlap] procedure.
The border of a word is the longest subword that is both a prefix and suffix of the word. You can compute the border of a word using the StringTools[Border] procedure. For efficiency, you can compute the length of the border without actually constructing it using StringTools[BorderLength]. The border array of a word is the list of the lengths of the borders of its prefixes.
Border( Fibonacci( 8 ) );
seq( evalb( Border( Fibonacci( n + 2 ) ) = Fibonacci( n ) ), n = 1 .. 10 );
BorderArray( Fibonacci( 6 ) );
Overlap( "abc", "bcd" );
f8 := Fibonacci( 8 ):
Overlap( f8, f8 );
The new StringTools[IsVowel] procedure recognizes the upper and lower case English language vowels: a, e, i, o, and u.
Select( IsVowel, "facetious" );
The StringTools[CamelCase] procedure performs a conversion that is best explained by the following example.
CamelCase( "linearalgebraicgroups" );
The new StringTools[Visible] procedure is an aid for examining strings that contain control characters. It replaces non-printing characters with ASCII escape codes.
Visible( Random( 10 ) );
The new StringTools[Anagrams] procedure searches for anagrams of a given word (string) in a list of words (strings).
Anagrams( "edit", [ "foo", "diet", "bar", "tide", "baz", "edit", "dite", "foobar" ] );
Two new subpackages have been added to the Student package, LinearAlgebra and Precalculus. For more information, see New Packages in Maple 9.
The Calculus1 subpackage in the Student package now contains interactive tutors, which are graphical user interfaces that help you work through particular calculus problems. For more information, see Student[Calculus1][InteractiveOverview].
The SumTools package now contains functions that help you find closed forms of definite and indefinite sums. The package consists of three functions and three subpackages.
Functions for Computing Closed Forms
The functions for computing closed forms of definite and indefinite sums are the following.
Summation: compute closed forms of definite and indefinite sums
DefiniteSummation: compute closed forms of definite sums
IndefiniteSummation: compute closed forms of indefinite sums
The DefiniteSum Package
The DefiniteSum package contains tools for computing closed forms of definite sums.
CreativeTelescoping: compute closed forms of definite sums using the creative telescoping method
Definite: compute closed forms of definite sums using the general routine
pFqToStandardFunctions: compute closed forms of definite sums using the conversion method where the hypergeometric series is used as an intermediate representation
Telescoping: compute closed forms of definite sums using the classical telescoping method
The IndefiniteSum Subpackage
The IndefiniteSum package contains tools for computing closed forms of indefinite sums.
AccurateSummation: indefinite sums using the method of accurate summation
AddIndefiniteSum: library extension mechanism
Hypergeometric: indefinite sums of j-fold hypergeometric terms
Indefinite: general routine for computing closed forms of indefinite sums
Polynomial: indefinite sums of polynomials
Rational: indefinite sums of rational functions
RemoveIndefiniteSum: library extension mechanism
The Hypergeometric Subpackage
The Hypergeometric package contains tools for working with hypergeometric terms in general, and for finding closed forms of definite and indefinite sums of hypergeometric term.
Normal forms of rational functions and of hypergeometric terms: MultiplicativeDecomposition, PolynomialNormalForm, RationalCanonicalForm, SumDecomposition
Algorithms for definite and indefinite sums of hypergeometric type: ExtendedGosper, ExtendedZeilberger, Gosper, IsZApplicable, KoepfGosper, KoepfZeilberger, LowerBound, MinimalZpair, Zeilberger, ZeilbergerRecurrence, ZpairDirect
Applications: DefiniteSum, IndefiniteSum, WZMethod
Other functions: AreSimilar, ConjugateRTerm, IsHolonomic, IsHypergeometricTerm, IsProperHypergeometricTerm, Verify
The SumTools[Hypergeometric][AccurateSummation] function has been superseded by the SumTools[IndefiniteSum][AccurateSummation] function.
The following new functions have been added to the SumTools[Hypergeometric] package:
IsZApplicable: An implementation of a necessary and sufficient condition for the termination of Zeilberger's algorithm to hypergeometric terms.
T1 := 1/(n*k+n+1)*binomial(n,k+1) +
T2 := (-1)^k*1/(n*k+1)*binomial(n+1,k)*binomial(2*n-2*k-1,n-1);
LowerBound: An implementation of an algorithm to compute a lower bound for the order of the telescopers for a given bivariate hypergeometric term.
T3 := 1/(n*(k+1)+1)*binomial(2*n,k+1)-1/(n*k+1)*binomial(2*n,k)+
ExtendedZeilberger: An implementation of an algorithm which computes the minimal Z-pairs for a class of sums of hypergeometric terms.
T4 := (-1)^k*binomial(m,k)*binomial(2*k,k)*1/2^(2*k);
V := Sum(T4,m=0..n);
_EnvDoubleSum := true:
Sum(V,k=0..n) = DefiniteSum(V,n,k,0..n);
KoepfGosper and KoepfZeilberger: Implementation of W. Koepf's extension to Gosper's algorithm and Zeilberger's algorithm, respectively.
T5 := n*(n/2)!;
Sum(T5,n) = KoepfGosper(T5,n);
T6 := binomial(2/3*n,2*k);
Zpair := KoepfZeilberger(T6,n,k,En);
MinimalZpair: A combination of various algorithms for computing the minimal Z-pairs of hypergeometric terms.
T7 := 1/(3*n+20*k+2)^3;
T8 := 1/(n*(k+1)-1)/(n-2*k-4)/(2*n+k+4)!-1/(n*k-1)/(n-2*k-2)/(2*n+k+3)!+1/(n-2*k-2)/(2*n+k+3)!;
Zpair := MinimalZpair(T8,n,k,En):
As previously demonstrated using the IsZApplicable function, you cannot apply Zeilberger's algorithm to T2.
Error, (in SumTools:-Hypergeometric:-MinimalZpair) Zeilberger's algorithm is not applicable
The VectorCalculus package has been enhanced in several ways.
The Divergence, Curl, Gradient, and Laplacian operators now return the form of the operator if invoked with no arguments. Note that coordinate names must have been assigned previously (see SetCoordinates).
All of the VectorCalculus operations that compute integrals now take an optional argument, inert. When this option is specified, the command returns the unevaluated integral representation of that computation.
The top-level D command has been extended to work with Vectors.
The TangentLine and TangentPlane commands have been extended. You can now specify the curve for TangentLine and the surface for TangentPlane as simple expressions.
The Worksheet package has been updated to support the new XML worksheet format. Various utilities for converting Maple worksheets between the previous and new format have been added to the package.
The Process and Validate functions are not required in Maple 9. They have been removed.
The XMLTools package has been updated with significant new functionality, including namespace support, XSLT transforms, and a validating XML parser.
Three new exports form the core of the functionality improvements in this package: XMLTools[ParseString], XMLTools[ParseFile], and XMLTools[Transform].
The XMLTools[ParseString] (and related XMLTools[ParseFile]) command is a Maple interface to the Xerces validating XML parser.
with( XMLTools ):
x := ParseString( "<m:math xmlns:m='http://www.w3.org/Math/'><m:apply><m:sin/><m:ci>θ</m:ci></m:apply></m:math>" ):
Print( x );
<m:math xmlns:m = 'http://www.w3.org/Math/'>
ElementName( FirstChild( x ) );
ElementType( FirstChild( x ) );
The XMLTools[ParseFile] command takes the name of an XML file as an argument, and returns the internal representation of the XML data.
The new routine XMLTools[Transform] applies an XSL stylesheet to an XML document instance.
ss := "<xsl:stylesheet xmlns:xsl='http://www.w3.org/1999/XSL/Transform' version='1.0'><xsl:output method='xml' indent='yes'/><xsl:template match='a'><A><xsl:apply-templates select='b'/></A></xsl:template><xsl:template match='b'>B:<xsl:value-of select='@d'/></xsl:template></xsl:stylesheet>":
doc := "<a><b d='foo'/></a>":
Print( ss );
<stylesheet xsl='http://www.w3.org/1999/XSL/Transform' version='1.0'>
<output method='xml' indent='yes'/>
Print( doc );
res := ToString( Transform( ParseString( ss ), ParseString( doc ) ) ):
Print( res );
<?xml version='1.0' encoding='ISO-8859-1' ?>
Note that the internal representation of XML documents has changed significantly in this release to support namespaces and DTD internal subsets.
The JoinEntities, SeparateEntities, MakeElement, and DocumentIterator functions have been removed.
The CData, Comment, Element, and ProcessingInstruction functions have been superseded by the XMLCData, XMLComment, XMLElement, and XMLProcessingInstruction functions, respectively.
Enhanced Packages in Maple 9: Part 1