On-line construction of suffix trees View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1995-09

AUTHORS

E. Ukkonen

ABSTRACT

An on-line algorithm is presented for constructing the suffix tree for a given string in time linear in the length of the string. The new algorithm has the desirable property of processing the string symbol by symbol from left to right. It always has the suffix tree for the scanned part of the string ready. The method is developed as a linear-time version of a very simple algorithm for (quadratic size) suffixtries. Regardless of its quadratic worst case this latter algorithm can be a good practical method when the string is not too long. Another variation of this method is shown to give, in a natural way, the well-known algorithms for constructing suffix automata (DAWGs). More... »

PAGES

249-260

References to SciGraph publications

  • 1993. Approximate string-matching over suffix trees in COMBINATORIAL PATTERN MATCHING
  • 1985. The Myriad Virtues of Subword Trees in COMBINATORIAL ALGORITHMS ON WORDS
  • 1993-11. Approximate string matching with suffix automata in ALGORITHMICA
  • 1988. String matching with constraints in MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 1988
  • 1987-08. Time optimal left to right construction of position trees in ACTA INFORMATICA
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/bf01206331

    DOI

    http://dx.doi.org/10.1007/bf01206331

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1024230952


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, University of Helsinki, P.O. Box 26, FIN-00014, Teollisuuskatu 23", 
              "id": "http://www.grid.ac/institutes/grid.7737.4", 
              "name": [
                "Department of Computer Science, University of Helsinki, P.O. Box 26, FIN-00014, Teollisuuskatu 23"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Ukkonen", 
            "givenName": "E.", 
            "id": "sg:person.01321052663.04", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01321052663.04"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bfb0017130", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052008139", 
              "https://doi.org/10.1007/bfb0017130"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01769703", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022389860", 
              "https://doi.org/10.1007/bf01769703"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0029808", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041720151", 
              "https://doi.org/10.1007/bfb0029808"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00292114", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024511249", 
              "https://doi.org/10.1007/bf00292114"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-82456-2_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019221734", 
              "https://doi.org/10.1007/978-3-642-82456-2_6"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1995-09", 
        "datePublishedReg": "1995-09-01", 
        "description": "An on-line algorithm is presented for constructing the suffix tree for a given string in time linear in the length of the string. The new algorithm has the desirable property of processing the string symbol by symbol from left to right. It always has the suffix tree for the scanned part of the string ready. The method is developed as a linear-time version of a very simple algorithm for (quadratic size) suffixtries. Regardless of its quadratic worst case this latter algorithm can be a good practical method when the string is not too long. Another variation of this method is shown to give, in a natural way, the well-known algorithms for constructing suffix automata (DAWGs).", 
        "genre": "article", 
        "id": "sg:pub.10.1007/bf01206331", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1047644", 
            "issn": [
              "0178-4617", 
              "1432-0541"
            ], 
            "name": "Algorithmica", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "14"
          }
        ], 
        "keywords": [
          "suffix tree", 
          "line algorithm", 
          "algorithm", 
          "new algorithm", 
          "latter algorithm", 
          "trees", 
          "strings", 
          "desirable properties", 
          "scanned part", 
          "simple algorithm", 
          "worst case", 
          "natural way", 
          "suffix automaton", 
          "line construction", 
          "symbols", 
          "method", 
          "version", 
          "practical method", 
          "way", 
          "automata", 
          "construction", 
          "time", 
          "properties", 
          "part", 
          "cases", 
          "length", 
          "rights", 
          "variation", 
          "string symbol", 
          "linear-time version", 
          "suffixtries", 
          "quadratic worst case", 
          "best practical method"
        ], 
        "name": "On-line construction of suffix trees", 
        "pagination": "249-260", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1024230952"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf01206331"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf01206331", 
          "https://app.dimensions.ai/details/publication/pub.1024230952"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2021-11-01T18:01", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/article/article_278.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/bf01206331"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/bf01206331'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/bf01206331'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf01206331'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf01206331'


     

    This table displays all metadata directly associated to this object as RDF triples.

    111 TRIPLES      22 PREDICATES      64 URIs      51 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf01206331 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author Nd9455ce3acd04ec6a8e2804f1ea3b2e3
    4 schema:citation sg:pub.10.1007/978-3-642-82456-2_6
    5 sg:pub.10.1007/bf00292114
    6 sg:pub.10.1007/bf01769703
    7 sg:pub.10.1007/bfb0017130
    8 sg:pub.10.1007/bfb0029808
    9 schema:datePublished 1995-09
    10 schema:datePublishedReg 1995-09-01
    11 schema:description An on-line algorithm is presented for constructing the suffix tree for a given string in time linear in the length of the string. The new algorithm has the desirable property of processing the string symbol by symbol from left to right. It always has the suffix tree for the scanned part of the string ready. The method is developed as a linear-time version of a very simple algorithm for (quadratic size) suffixtries. Regardless of its quadratic worst case this latter algorithm can be a good practical method when the string is not too long. Another variation of this method is shown to give, in a natural way, the well-known algorithms for constructing suffix automata (DAWGs).
    12 schema:genre article
    13 schema:inLanguage en
    14 schema:isAccessibleForFree false
    15 schema:isPartOf N6e51fc4b55144cd2adf1dcd626762d3f
    16 Nf4db241c4eb145b1a8f5ca344386a0c9
    17 sg:journal.1047644
    18 schema:keywords algorithm
    19 automata
    20 best practical method
    21 cases
    22 construction
    23 desirable properties
    24 latter algorithm
    25 length
    26 line algorithm
    27 line construction
    28 linear-time version
    29 method
    30 natural way
    31 new algorithm
    32 part
    33 practical method
    34 properties
    35 quadratic worst case
    36 rights
    37 scanned part
    38 simple algorithm
    39 string symbol
    40 strings
    41 suffix automaton
    42 suffix tree
    43 suffixtries
    44 symbols
    45 time
    46 trees
    47 variation
    48 version
    49 way
    50 worst case
    51 schema:name On-line construction of suffix trees
    52 schema:pagination 249-260
    53 schema:productId N6202de50e16545c59e7458fee1c5b257
    54 N841eea9f1a7d4e35880d52feb611874e
    55 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024230952
    56 https://doi.org/10.1007/bf01206331
    57 schema:sdDatePublished 2021-11-01T18:01
    58 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    59 schema:sdPublisher N32a7dfe0a1ad48fa862f185cfe50d1d8
    60 schema:url https://doi.org/10.1007/bf01206331
    61 sgo:license sg:explorer/license/
    62 sgo:sdDataset articles
    63 rdf:type schema:ScholarlyArticle
    64 N32a7dfe0a1ad48fa862f185cfe50d1d8 schema:name Springer Nature - SN SciGraph project
    65 rdf:type schema:Organization
    66 N6202de50e16545c59e7458fee1c5b257 schema:name doi
    67 schema:value 10.1007/bf01206331
    68 rdf:type schema:PropertyValue
    69 N6e51fc4b55144cd2adf1dcd626762d3f schema:volumeNumber 14
    70 rdf:type schema:PublicationVolume
    71 N841eea9f1a7d4e35880d52feb611874e schema:name dimensions_id
    72 schema:value pub.1024230952
    73 rdf:type schema:PropertyValue
    74 Nd9455ce3acd04ec6a8e2804f1ea3b2e3 rdf:first sg:person.01321052663.04
    75 rdf:rest rdf:nil
    76 Nf4db241c4eb145b1a8f5ca344386a0c9 schema:issueNumber 3
    77 rdf:type schema:PublicationIssue
    78 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    79 schema:name Mathematical Sciences
    80 rdf:type schema:DefinedTerm
    81 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    82 schema:name Pure Mathematics
    83 rdf:type schema:DefinedTerm
    84 sg:journal.1047644 schema:issn 0178-4617
    85 1432-0541
    86 schema:name Algorithmica
    87 schema:publisher Springer Nature
    88 rdf:type schema:Periodical
    89 sg:person.01321052663.04 schema:affiliation grid-institutes:grid.7737.4
    90 schema:familyName Ukkonen
    91 schema:givenName E.
    92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01321052663.04
    93 rdf:type schema:Person
    94 sg:pub.10.1007/978-3-642-82456-2_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019221734
    95 https://doi.org/10.1007/978-3-642-82456-2_6
    96 rdf:type schema:CreativeWork
    97 sg:pub.10.1007/bf00292114 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024511249
    98 https://doi.org/10.1007/bf00292114
    99 rdf:type schema:CreativeWork
    100 sg:pub.10.1007/bf01769703 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022389860
    101 https://doi.org/10.1007/bf01769703
    102 rdf:type schema:CreativeWork
    103 sg:pub.10.1007/bfb0017130 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052008139
    104 https://doi.org/10.1007/bfb0017130
    105 rdf:type schema:CreativeWork
    106 sg:pub.10.1007/bfb0029808 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041720151
    107 https://doi.org/10.1007/bfb0029808
    108 rdf:type schema:CreativeWork
    109 grid-institutes:grid.7737.4 schema:alternateName Department of Computer Science, University of Helsinki, P.O. Box 26, FIN-00014, Teollisuuskatu 23
    110 schema:name Department of Computer Science, University of Helsinki, P.O. Box 26, FIN-00014, Teollisuuskatu 23
    111 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...