On-line construction of suffix trees View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


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/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Helsinki", 
              "id": "https://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": "https://doi.org/10.1016/0304-3975(85)90157-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019022044"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(85)90157-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019022044"
            ], 
            "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"
          }, 
          {
            "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/bf01769703", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022389860", 
              "https://doi.org/10.1007/bf01769703"
            ], 
            "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": "https://doi.org/10.1145/360825.360855", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027390472"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(86)90041-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036552598"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(86)90041-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036552598"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0885-064x(88)90008-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040349924"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/321941.321946", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040652581"
            ], 
            "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/bfb0017130", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052008139", 
              "https://doi.org/10.1007/bfb0017130"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/swat.1973.13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086215622"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1991.185445", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086357260"
            ], 
            "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": "research_article", 
        "id": "sg:pub.10.1007/bf01206331", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1047644", 
            "issn": [
              "0178-4617", 
              "1432-0541"
            ], 
            "name": "Algorithmica", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "14"
          }
        ], 
        "name": "On-line construction of suffix trees", 
        "pagination": "249-260", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "73706600ebc02182d9709b550b38a06ae4603161cfc861c83a8d8f31ab1b3d27"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf01206331"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1024230952"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf01206331", 
          "https://app.dimensions.ai/details/publication/pub.1024230952"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T13:28", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000370_0000000370/records_46741_00000001.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/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.

    102 TRIPLES      21 PREDICATES      39 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf01206331 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author N0b4bb8587dc145d09ca894cc55a3a503
    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 https://doi.org/10.1016/0304-3975(85)90157-4
    10 https://doi.org/10.1016/0304-3975(86)90041-1
    11 https://doi.org/10.1016/0885-064x(88)90008-8
    12 https://doi.org/10.1109/sfcs.1991.185445
    13 https://doi.org/10.1109/swat.1973.13
    14 https://doi.org/10.1145/321941.321946
    15 https://doi.org/10.1145/360825.360855
    16 schema:datePublished 1995-09
    17 schema:datePublishedReg 1995-09-01
    18 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).
    19 schema:genre research_article
    20 schema:inLanguage en
    21 schema:isAccessibleForFree true
    22 schema:isPartOf N3d0e08cf9ec24c158317544df01887bc
    23 N7db65ad8d20f43b7a3d5282c8b1c0edf
    24 sg:journal.1047644
    25 schema:name On-line construction of suffix trees
    26 schema:pagination 249-260
    27 schema:productId Nae6f04b410ef450aa5fd69451e86e67d
    28 Nd0ebca798ba44d9c98f5f103332da716
    29 Nfc5c7fa7ac8e4e27a00a18b38e956c44
    30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024230952
    31 https://doi.org/10.1007/bf01206331
    32 schema:sdDatePublished 2019-04-11T13:28
    33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    34 schema:sdPublisher N37e6f14f255c4261843bd80d9933d51f
    35 schema:url http://link.springer.com/10.1007/BF01206331
    36 sgo:license sg:explorer/license/
    37 sgo:sdDataset articles
    38 rdf:type schema:ScholarlyArticle
    39 N0b4bb8587dc145d09ca894cc55a3a503 rdf:first sg:person.01321052663.04
    40 rdf:rest rdf:nil
    41 N37e6f14f255c4261843bd80d9933d51f schema:name Springer Nature - SN SciGraph project
    42 rdf:type schema:Organization
    43 N3d0e08cf9ec24c158317544df01887bc schema:volumeNumber 14
    44 rdf:type schema:PublicationVolume
    45 N7db65ad8d20f43b7a3d5282c8b1c0edf schema:issueNumber 3
    46 rdf:type schema:PublicationIssue
    47 Nae6f04b410ef450aa5fd69451e86e67d schema:name dimensions_id
    48 schema:value pub.1024230952
    49 rdf:type schema:PropertyValue
    50 Nd0ebca798ba44d9c98f5f103332da716 schema:name readcube_id
    51 schema:value 73706600ebc02182d9709b550b38a06ae4603161cfc861c83a8d8f31ab1b3d27
    52 rdf:type schema:PropertyValue
    53 Nfc5c7fa7ac8e4e27a00a18b38e956c44 schema:name doi
    54 schema:value 10.1007/bf01206331
    55 rdf:type schema:PropertyValue
    56 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    57 schema:name Mathematical Sciences
    58 rdf:type schema:DefinedTerm
    59 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    60 schema:name Pure Mathematics
    61 rdf:type schema:DefinedTerm
    62 sg:journal.1047644 schema:issn 0178-4617
    63 1432-0541
    64 schema:name Algorithmica
    65 rdf:type schema:Periodical
    66 sg:person.01321052663.04 schema:affiliation https://www.grid.ac/institutes/grid.7737.4
    67 schema:familyName Ukkonen
    68 schema:givenName E.
    69 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01321052663.04
    70 rdf:type schema:Person
    71 sg:pub.10.1007/978-3-642-82456-2_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019221734
    72 https://doi.org/10.1007/978-3-642-82456-2_6
    73 rdf:type schema:CreativeWork
    74 sg:pub.10.1007/bf00292114 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024511249
    75 https://doi.org/10.1007/bf00292114
    76 rdf:type schema:CreativeWork
    77 sg:pub.10.1007/bf01769703 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022389860
    78 https://doi.org/10.1007/bf01769703
    79 rdf:type schema:CreativeWork
    80 sg:pub.10.1007/bfb0017130 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052008139
    81 https://doi.org/10.1007/bfb0017130
    82 rdf:type schema:CreativeWork
    83 sg:pub.10.1007/bfb0029808 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041720151
    84 https://doi.org/10.1007/bfb0029808
    85 rdf:type schema:CreativeWork
    86 https://doi.org/10.1016/0304-3975(85)90157-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019022044
    87 rdf:type schema:CreativeWork
    88 https://doi.org/10.1016/0304-3975(86)90041-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036552598
    89 rdf:type schema:CreativeWork
    90 https://doi.org/10.1016/0885-064x(88)90008-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040349924
    91 rdf:type schema:CreativeWork
    92 https://doi.org/10.1109/sfcs.1991.185445 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086357260
    93 rdf:type schema:CreativeWork
    94 https://doi.org/10.1109/swat.1973.13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086215622
    95 rdf:type schema:CreativeWork
    96 https://doi.org/10.1145/321941.321946 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040652581
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1145/360825.360855 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027390472
    99 rdf:type schema:CreativeWork
    100 https://www.grid.ac/institutes/grid.7737.4 schema:alternateName University of Helsinki
    101 schema:name Department of Computer Science, University of Helsinki, P.O. Box 26, FIN-00014, Teollisuuskatu 23
    102 rdf:type schema:Organization
     




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


    ...