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 Ne5e55f38bc88465fbb21b09eee1c5d6e
    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 N14c23864838249cc8925f32c98481c37
    16 Nc0a34b2eaf0a496db01212f6d81a48ce
    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 N2fb4adc05b354e1681943906c632b716
    54 Naed9b8847bd04d44a5f672513ba0d262
    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 Nba7e1c6fe503460eb514585e9853a5ac
    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 N14c23864838249cc8925f32c98481c37 schema:volumeNumber 14
    65 rdf:type schema:PublicationVolume
    66 N2fb4adc05b354e1681943906c632b716 schema:name doi
    67 schema:value 10.1007/bf01206331
    68 rdf:type schema:PropertyValue
    69 Naed9b8847bd04d44a5f672513ba0d262 schema:name dimensions_id
    70 schema:value pub.1024230952
    71 rdf:type schema:PropertyValue
    72 Nba7e1c6fe503460eb514585e9853a5ac schema:name Springer Nature - SN SciGraph project
    73 rdf:type schema:Organization
    74 Nc0a34b2eaf0a496db01212f6d81a48ce schema:issueNumber 3
    75 rdf:type schema:PublicationIssue
    76 Ne5e55f38bc88465fbb21b09eee1c5d6e rdf:first sg:person.01321052663.04
    77 rdf:rest rdf:nil
    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)


    ...